寻找长度为k的子序列，其和等于给定和

Question

给定数组A和sum，我想知道是否存在长度为K的子序列，以便子序列中所有元素的和等于给定的sum。

代码：

for i in(1,N):
    for len  in (i-1,0):
        for sum in (0,Sum of all element)
            Possible[len+1][sum] |= Possible[len][sum-A[i]]

时间复杂度O(N^2和).有没有办法提高O(N.Sum)的时间复杂度？

Answer 1

我的函数将k相邻数组项的窗口移到数组A上，并保持对数据的总和，直到匹配搜索失败为止。

int getSubSequenceStart(int A[], size_t len, int sum, size_t k)
{    
    int sumK = 0;

    assert(len > 0);
    assert(k <= len);

    //  compute sum for first k items
    for (int i = 0; i < k; i++)
    {
        sumK += A[i];
    }

    //  shift k-window upto end of A
    for (int j = k; j < len; j++)
    {
        if (sumK == sum)
        {
            return j - k;
        }

        sumK += A[j] - A[j - k];
    }

    return -1;
}

复杂度为线性和阵列A的长度。

非连续通用子数组情况下的更新：

要找到一个可能不连续的子数组，您可以将您的问题转化为子集和问题，方法是从A的每个元素中减去sum/k，并寻找一个和为零的子集。众所周知，子集和问题的复杂性是指数的。因此，除非数组A具有特殊的属性，否则您不能期望使用线性算法。

Answer 2

设is_subset_sum(int set[], int n, int sum)是确定是否存在和等于和的set[]子集的函数。n是set[]中的元素数。

is_subset_sum problem可分为两个子问题

• 包含最后一个元素，n= n-1，sum = sum -setn n-1。
• 排除最后一个元素，重复n= n-1。

如果上述任何子问题返回true，则返回true。

下面是is_subset_sum()问题的递归公式.

is_subset_sum(set, n, sum) = is_subset_sum(set, n-1, sum) || is_subset_sum(set, n-1, sum-set[n-1])

Base Cases:

is_subset_sum(set, n, sum) = false, if sum > 0 and n == 0

is_subset_sum(set, n, sum) = true, if sum == 0 

我们可以用动态规划来解决伪多项式时间中的问题。我们创建一个布尔2D表子集，并以自下而上的方式填充它。如果集合0.j-1的子集和等于i，否则为false，则subseti的值将为true。最后，我们返回子集和。

解的时间复杂度为O(sum*n)。

在C中的实现

// A Dynamic Programming solution for subset sum problem

#include <stdio.h>

// Returns true if there is a subset of set[] with sun equal to given sum

bool is_subset_sum(int set[], int n, int sum) {

    // The value of subset[i][j] will be true if there is a

    // subset of set[0..j-1] with sum equal to i

    bool subset[sum+1][n+1];

    // If sum is 0, then answer is true

    for (int i = 0; i <= n; i++)

      subset[0][i] = true;

    // If sum is not 0 and set is empty, then answer is false

    for (int i = 1; i <= sum; i++)

      subset[i][0] = false;

     // Fill the subset table in botton up manner

     for (int i = 1; i <= sum; i++) {

       for (int j = 1; j <= n; j++) {

         subset[i][j] = subset[i][j-1];

         if (i >= set[j-1])

           subset[i][j] = subset[i][j] || subset[i - set[j-1]][j-1];
       }

     }

    /* // uncomment this code to print table

     for (int i = 0; i <= sum; i++) {

       for (int j = 0; j <= n; j++)

          printf ("%4d", subset[i][j]);

       printf("\n");

     } */

     return subset[sum][n];
}

// Driver program to test above function

int main() {

  int set[] = {3, 34, 4, 12, 5, 2};

  int sum = 9;

  int n = sizeof(set)/sizeof(set[0]);

  if (is_subset_sum(set, n, sum) == true)

     printf("Found a subset with given sum");

  else

     printf("No subset with given sum");

  return 0;
}

Answer 3

编辑：

这实际上可以在没有线性时间队列的情况下得到解决(允许负数)。

C#代码：

bool SubsequenceExists(int[] a, int k, int sum)
{
    int currentSum = 0;
    if (a.Length < k) return false;

    for (int i = 0; i < a.Length; i++)
    {
        if (i < k)
        {
            currentSum += a[i];
            continue;
        }

        if (currentSum == sum) return true;
        currentSum += a[i] - a[i-k];
    }
    return false;
}

原始答案：

假设您可以使用长度为K的队列，那么类似的事情应该在线性时间内完成。

C#代码：

bool SubsequenceExists(int[] a, int k, int sum)
{
    int currentSum = 0;
    var queue = new Queue<int>();

    for (int i = 0; i < a.Length; i++)
    {
        if (i < k)
        {
            queue.Enqueue(a[i]);
            currentSum += a[i];
            continue;
        }

        if (currentSum == sum) return true;
        currentSum -= queue.Dequeue();
        queue.Enqueue(a[i]);
        currentSum += a[i];
    }
    return false;
}

这背后的逻辑非常简单：

1. 我们使用第一个K元素填充队列，同时将其和存储在某处。
2. 如果得到的和不等于sum，那么我们从队列中排出一个元素，并从A中添加下一个元素(同时更新和)。
3. 我们重复第2步，直到我们到达序列的末尾或找到匹配的子序列。

塔达！