30

入力配列が与えられると、これまでに見つかった合計と開始位置を追跡することにより、線形時間で合計が 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;
}

私の質問は、数値の混合セット (正の数値と負の数値の両方) に対してもそのような解決策があるかどうかです。

4

7 に答える 7

24

正の数と負の数の両方の場合の線形時間アルゴリズムはありません。

合計が になるすべてのサブ配列が必要なのでK、アルゴリズムの時間の複雑さは、サブ配列の結果のセットのサイズよりも優れていることはありません。そして、このサイズは 2 次かもしれません。たとえば、[K, -K, K, -K, K, -K, ...]正の 'K' で始まり、正の 'K' で終わる のサブ配列には、必要な合計があり、そのようなサブ配列は N 2 /8 あります。

それでも、O(N) の追加スペースが利用可能な場合、O(N) の予想時間で結果を取得することが可能です。

配列の各要素のプレフィックスの合計を計算し、ペア(prefix_sum, index)をハッシュ マップに挿入します。ここprefix_sumで、 はキー、indexはこのキーに関連付けられた値です。このハッシュ マップを検索prefix_sum - Kして、結果のサブ配列が開始する 1 つまたは複数の配列インデックスを取得します。

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)
于 2013-02-19T09:02:11.633 に答える
7

Javaでコード化された@Evgeny Kluevによる解決策と少しの説明。

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);
    }
}
于 2015-11-02T07:23:52.140 に答える
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, ]
于 2014-05-06T06:30:29.173 に答える
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;
    }
}
于 2016-04-07T21:47:14.147 に答える
0

C ++でコード化された@Evgeny Kluevによって与えられた解決策

#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;
}
于 2017-11-15T09:54:26.373 に答える