给定一个输入数组查找与给定的款项请在所有子阵 [英] Given an input array find all subarrays with given sum K

问题描述

给定输入数组，我们可以找到一个子阵列款项K（给予）的线性时间，通过跟踪总和迄今为止发现的开始位置。如果当前的总和变得大于K个我们保持除去开始位置的元素，直到我们得到当前总和与所述; = K。

Given an input array we can find a single sub-array which sums to K (given) in linear time, by keeping track of sum found so far and the start position. If the current sum becomes greater than the K we keep removing elements from start position until we get current sum <= K.

我发现从geeksforgeeks样品code和更新，它返回所有这些可能的集合。但假设是输入阵列由仅+已经号码。

I found sample code from geeksforgeeks and updated it to return all such possible sets. But the assumption is that the input array consists of only +ve numbers.

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;
}

我的问题是我们有混合组数字太（正数和负数）？

My question is do we have such a solution for mixed set of numbers too (both positive and negative numbers)?

推荐答案

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

There is no linear-time algorithm for the case of both positive and negative numbers.

由于您所需要的所有子阵列其总和 K ，任意时间算法的复杂度不能大于所产生的副阵列组的大小更好。和这个尺寸可以是二次的。例如，任何子阵列的 [K，-K，K，-K，K，-K，...] ，并开始在积极的K结尾具有所需的总和，并存在N ² / 8这样的子阵列。

Since you need all sub-arrays which sum to K, time complexity of any algorithm cannot be better than size of the resulting set of sub-arrays. And this size may be quadratic. For example, any sub-array of [K, -K, K, -K, K, -K, ...], starting and ending at positive 'K' has the required sum, and there are N²/8 such sub-arrays.

不过有可能得到的结果为O（N）预计时间，如果O（N），额外的空间可用。

Still it is possible to get the result in O(N) expected time if O(N) additional space is available.

计算preFIX总和的阵列中的每个元素并插入一对（prefix_sum，指数）来一个散列映射，其中 prefix_sum 是关键，首页与此键关联的值。搜索 prefix_sum - 在这个散列映射氏/ code>来获得一个或多个数组索引，其中所产生的子阵列启动：

Compute prefix sum for each element of the array and insert the pair (prefix_sum, index) to a hash map, where prefix_sum is the key and index is the value associated with this key. Search prefix_sum - K in this hash map to get one or several array indexes where the resulting sub-arrays start:

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)

这篇关于给定一个输入数组查找与给定的款项请在所有子阵的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！