给定输入数组,找到给定总和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)到哈希映射中,其中prefix_sum键index是键,并且是与此键关联的值.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)

Answer 2

@Evgeny Kluev给出的解决方案用Java编写,稍作解释.

public static void main(String[] args) {
    int[] INPUT = {5, 6, 1, -2, -4, 3, 1, 5};
    printSubarrays(INPUT, 5);
}

private static void printSubarrays(int[] input, int k) {
    Map<Integer, List<Integer>> map = new HashMap<Integer, List<Integer>>();
    List<Integer> initial = new ArrayList<Integer>();
    initial.add(-1);
    map.put(0, initial);
    int preSum = 0;

    // Loop across all elements of the array
    for(int i=0; i< input.length; i++) {
        preSum += input[i];
        // If point where sum = (preSum - k) is present, it means that between that 
        // point and this, the sum has to equal k
        if(map.containsKey(preSum - k)) {   // Subarray found 
            List<Integer> startIndices = map.get(preSum - k);
            for(int start : startIndices) {
                System.out.println("Start: "+ (start+1)+ "\tEnd: "+ i);
            }
        }

        List<Integer> newStart = new ArrayList<Integer>();
        if(map.containsKey(preSum)) { 
            newStart = map.get(preSum);
        }
        newStart.add(i);
        map.put(preSum, newStart);
    }
}