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

Question

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

32

对于给定的输入数组，我们可以在线性时间内找到一个子数组，其总和为给定的K值，方法是通过跟踪当前已发现的总和和起始位置。如果当前的总和大于K，我们将删除从起始位置开始的元素，直到当前总和小于等于K。

我从geeksforgeeks找到了示例代码，并更新了它以返回所有可能的集合。但假设输入数组仅由正数组成。

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

我的问题是，我们是否也有针对混合数字集（包括正数和负数）的解决方案？

- user1071840

1

@jogojapan，已经移除了C++标签。但是，你指出的问题是不同的，那需要至少具有'k'个连续元素的子数组，并且具有最大和。我正在寻求任何长度的子数组，其和为给定值。 - user1071840

1

@jogojapan。为了获得最大总和，我们有Kadane算法，它可以处理正负输入，并可以更新为恰好包含“k”个元素。 - user1071840

@jogojapan。是的，我确定它可能有重复，但是我找不到，所以我发了一篇帖子。 - user1071840

@user1071840 好的。只是想提醒您，我会删除上面的评论，以免让任何人过早地点击“关闭投票”按钮。 - jogojapan

相关但不重复：http://stackoverflow.com/questions/13093602/finding-subarray-with-maximum-sum-number-of-elements - jogojapan

8个回答

8

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

- Menezes Sousa

1

二次时间：最坏情况下为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);
}

- Sameer Shrestha

0

按照 @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;
}

- N_Divyasri

0

这个问题与此处解决的组合问题非常相似：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;
    }
}

- Saurin

0

class Solution
{
    //Function to find a continuous sub-array which adds up to a given number.
    static ArrayList<Integer> subarraySum(int[] arr, int n, int s) 
    {
        ArrayList<Integer> res=new ArrayList<>();
       
        
        int i=0,j=0,sum=0;
        sum=sum+arr[i];
        if(s==0){
            res.add(-1);
                    return res;
        }
        while(true)
        {
                if(sum<s)
                {
                    j=j+1;
                    if(j>=n || i>=n){
                     res.add(-1);
                    return res;
                     }
                    sum=sum+arr[j];
                }else if(sum>s){
                    sum=sum-arr[i];
                    i=i+1;
                    if(sum==s){
                       res.add(i+1);
                    res.add(j+1);
                    return res; 
                    }
                }else{
                    res.add(i+1);
                    res.add(j+1);
                    return res;
                }   
                if(j>=n || i>=n){
                     res.add(-1);
                    return res;
                }
                
        }
        
        
    }
  
}

通过geeksforgeeks的165个测试用例。

- Nagappa L M

0

尝试使用这段代码，它可以为您工作：

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, ]

- Manmohan Soni

2

我知道这已经晚了几个月，但它是O(n^2)，因为你有两个数组迭代，都是从0到n。因此，你得到n（来自外部循环）* n（来自内部循环），这等于n^2。 - Anubhaw Arya

-2

我在几次面试中也遇到了这个问题，并想出了以下最佳方法：

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)的最佳解决方案。

- Aman Goel

1

OP想要的是子数组，其和为K。他不想要具有最大总和的子数组。 - CuriousCoder

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Evgeny Kluev · 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)