algorithm - Given an input array find all subarrays with given sum K

Question

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.

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)?

score 24 · Accepted Answer

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

由于您需要总和为的所有子数组，因此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)

score 7 · Accepted Answer

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

score 1 · Accepted Answer

二次时间：最坏情况下为 O(n2)。

private static void findSubArray(int[] is, int N) {
    System.out.println("Continuous sub array of " + Arrays.toString(is) + " whose sum is " + N + " is ");
    List<Integer> arry = new ArrayList<>(is.length);
    for (int i = 0; i < is.length; i++) {
        int tempI = is[i];
        arry.add(tempI);
        for (int j = i + 1; j < is.length; j++) {
            if (tempI + is[j] == N) {
                arry.add(is[j]);
                System.out.println(arry);

            } else if (tempI + is[j] < N) {
                arry.add(is[j]);
                tempI = tempI + is[j];
            } else {
                arry.clear();
                break;
            }
        }
    }

}
public static void main(String[] args) {
    findSubArray(new int[] { 42, 15, 12, 8, 6, 32 }, 26);

    findSubArray(new int[] { 12, 5, 31, 13, 21, 8 }, 49);

    findSubArray(new int[] { 15, 51, 7, 81, 5, 11, 25 }, 41);
}

score 0 · Accepted Answer

试试这个代码，这对你有用：

private static void printSubArrayOfRequiredSum(int[] array, int requiredSum) {
        for (int i = 0; i < array.length; i++) {
            String str = "[ ";
            int sum = 0;
            for (int j = i; j < array.length; j++) {
                sum = sum + array[j];
                str = str + array[j] + ", ";
                if (sum == requiredSum) {
                    System.out.println(" sum : " + sum + " array : " + str
                            + "]");
                    str = "[ ";
                    sum = 0;
                }
            }
        }
    }

使用这种方法，如：

 int array[] = { 3, 5, 6, 9, 14, 8, 2, 12, 7, 7 };
 printSubArrayOfRequiredSum(array, 14);

输出：

sum : 14 array : [ 3, 5, 6, ]
sum : 14 array : [ 14, ]
sum : 14 array : [ 2, 12, ]
sum : 14 array : [ 7, 7, ]

score 0 · Accepted Answer

@Evgeny Kluev 给出的解决方案，用 C++ 编码

#include<bits/stdc++.h>
using namespace std;
int c=0;
// Function to print subarray with sum as given sum
void subArraySum(int arr[], int n, int k)
{
   map<int,vector<int>>m1;
   m1[0].push_back(-1);
   int curr_sum=0;
   for(int i=0;i<n;i++){
       curr_sum=curr_sum+arr[i];
       if(m1.find(curr_sum-k)!=m1.end()){
           vector<int>a=m1[curr_sum-k];
           c+=m1[curr_sum-k].size();
           for(int j=0;j<a.size();j++){  // printing all indexes with sum=k
              cout<<a[j]+1<<" "<<i<<endl;
            }
        }
        m1[curr_sum].push_back(i);
    }  
 }
int main()
{
   int arr[] =  {10,2,0,10,0,10};
   int n = sizeof(arr)/sizeof(arr[0]);
   int sum = 10;
   subArraySum(arr, n, sum);
   cout<<c<<endl; //count of subarrays with given sum
   return 0;
}

score 0 · Accepted Answer

这个问题与这里解决的组合问题非常相似：http: //introcs.cs.princeton.edu/java/23recursion/Combinations.java.html

这是我的解决方案：

public static void main(String[] args) {
    int [] input = {-10, 0, 5, 10, 15, 20, 30};
    int expectedSum = 20;

    combination(new SumObj(new int[0]), new SumObj(input), expectedSum);
}

private static void combination(SumObj prefixSumObj, SumObj remainingSumObj, int expectedSum){
    if(prefixSumObj.getSum() == expectedSum){
        System.out.println(Arrays.toString(prefixSumObj.getElements()));
    } 

    for(int i=0; i< remainingSumObj.getElements().length ; i++){
        // prepare new prefix
        int [] newPrefixSumInput = new int[prefixSumObj.getElements().length + 1];
        System.arraycopy(prefixSumObj.getElements(), 0, newPrefixSumInput, 0, prefixSumObj.getElements().length);
        newPrefixSumInput[prefixSumObj.getElements().length] = remainingSumObj.getElements()[i];
        SumObj newPrefixSumObj = new SumObj(newPrefixSumInput);

        // prepare new remaining
        int [] newRemainingSumInput = new int[remainingSumObj.getElements().length - i - 1];            
        System.arraycopy(remainingSumObj.getElements(), i+1, newRemainingSumInput, 0, remainingSumObj.getElements().length - i - 1);
        SumObj newRemainingSumObj = new SumObj(newRemainingSumInput);

        combination(newPrefixSumObj, newRemainingSumObj, expectedSum);
    }
}

private static class SumObj {
    private int[] elements;
    private int sum;

    public SumObj(int[] elements) {
        this.elements = elements;
        this.sum = computeSum();
    }

    public int[] getElements() {
        return elements;
    }

    public int getSum() {
        return sum;
    }

    private int computeSum(){
        int tempSum = 0;
        for(int i=0; i< elements.length; i++){
            tempSum += elements[i];
        }
        return tempSum;
    }
}

score -2 · Accepted Answer

我在几次采访中也遇到了这个问题，并提出了以下最佳方法：

class MazSubArraySum {
public static void main(String[] args) {
    int[] a = { -2, -3, 4, -1, -2, 1, 5, -3 };
    System.out.println("Maximum contiguous sum is " + maxSubArraySum(a));

}

static int maxSubArraySum(int a[]) {
    int size = a.length;
    int currentindex = 0, end = 0, begin = 0;
    int max_so_far = Integer.MIN_VALUE, max_ending_here = 0;

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

        max_ending_here = max_ending_here + a[i];

        if (max_so_far < max_ending_here) {
            max_so_far = max_ending_here;
            begin = currentindex;
            end = i;

        }
        if (max_ending_here < 0) {
            max_ending_here = 0;
            currentindex++;

        }
    }

    System.out.println("begin and end: " + begin + "&" + end);
    return max_so_far;
}

}

下面是输出：

begin and end: 2&6
Maximum contiguous sum is 7

就时间和空间复杂度而言，上述解决方案是 O(n) 的最佳解决方案。

algorithm - Given an input array find all subarrays with given sum K

7 回答 7

Related

Reference