algorithm - 给定一个输入数组，找到给定总和 K 的所有子数组

Question

给定一个输入数组，我们可以通过跟踪到目前为止找到的总和和起始位置，找到一个在线性时间内总和为 K(给定)的子数组。如果当前总和大于 K，我们将继续从起始位置移除元素，直到我们得到当前总和 <= K。

我从 geeksforgeeks 找到了示例代码并对其进行了更新以返回所有此类可能的集合。但假设输入数组仅包含 +ve 个数字。

bool subArraySum(int arr[], int n, int sum)
{
    int curr_sum = 0, start = 0, i;
    bool found = false;

    for (i = 0; i <= n; i++)
    {
        while (curr_sum > sum && start < i)
        {
            curr_sum = curr_sum - arr[start];
            start++;
        }

        if (curr_sum == sum)
        {
            cout<<"Sum found in b/w indices: "<<start<<" & "<<(i-1)<<"\n";
            curr_sum -= arr[start];
            start++;
            found = true;
        }

        // Add this element to curr_sum
        if (i < n) {
          curr_sum = curr_sum + arr[i];
        }
    }

    return found;
}

我的问题是我们是否也有混合数字集(正数和负数)的解决方案？

Answer 1

对于正数和负数的情况，没有线性时间算法。

由于您需要总和为 K 的所有子数组，因此任何算法的时间复杂度都不能优于结果子数组集的大小。而这个尺寸可能是二次方的。例如，[K, -K, K, -K, K, -K, ...] 的任何子数组，以正“K”开始和结束都具有所需的总和，并且有 N²/8 个这样的子数组。

如果有 O(N) 的额外空间可用，仍然有可能在 O(N) 的预期时间内得到结果。

计算数组中每个元素的前缀和，并将对 (prefix_sum, index) 插入到 HashMap 中，其中 prefix_sum 是键，索引 是与此键关联的值。在此 HashMap 中搜索 prefix_sum - K 以获取一个或多个数组索引，其中生成的子数组开始:

hash_map[0] = [-1]
prefix_sum = 0
for index in range(0 .. N-1):
  prefix_sum += array[index]
  start_list = hash_map[prefix_sum - K]
  for each start_index in start_list:
    print start_index+1, index
  start_list2 = hash_map[prefix_sum]
  start_list2.append(index)