algorithm - サブシーケンス合計

Question

整数の配列が与えられた場合、合計してそれを返す[1, 2, -3, 1]サブシーケンスがあるかどうかを調べます(例: or )。 すべてのサブシーケンスをチェックするのは非効率的です。改善のアイデアはありますか？0[1, 2, -3][2, -3, 1]
O(n^2)

Answer 1

各要素が前の要素とその要素の合計に等しい新しい配列を作成します。

入力：

1  4 -3 -4  6  -7  8 -5

なる:

1  5  2  -2  4  -3  5  0
   ^                ^

次に、結果の配列で一致する要素を探します。

これらは関数の全体的な変化がゼロの位置を表しているため、それらの位置が i と k の場合、サブシーケンス (i+1, k) はゼロサム サブシーケンスであることがわかります。(この場合、[2:6])。

さらに、テーブル内のゼロは、サブシーケンス (0, k) がゼロサム サブシーケンスであることを示します。ルックアップの場合、ハッシュ テーブルまたはその他の高速衝突ロケーターにより、この O(N) が実行されます。

Answer 2

以下は、@Fabricio によって提案されたソリューションの Java 実装です。

    public static int countAllSubSequenceForZeroSum(int[] array) {
    int count = 0;
    Map<Integer, Integer> encounteredSum = new HashMap<>();
    int prev = array[0];
    if(prev == 0) {
        count++;
        System.out.println("Found at index: "+0);
    }
    for (int i = 1; i < array.length; i++) {
        prev += array[i];
        if(encounteredSum.containsKey(prev)) {
            System.out.println("Found at index: "+i+ " start index: "+encounteredSum.get(prev));
            printSequenceForZeroSum(array, i);
            count++;
        } else {
            encounteredSum.put(prev, i);
        }
    }
    return count;
}

public static void printSequenceForZeroSum(int[] array, int endIndex) {
    int sum = array[endIndex];
    while(sum!=0) {
        System.out.print(array[endIndex]+ "  ");
        sum += array[--endIndex];
    }
    System.out.println(array[endIndex]);
}

Answer 3

ファブリシオの答えに似たロジックを持つ C++ 実装。

pair<int, int> FindSubsequenceSum(const vector<int>& arr)      
{
  map<int, int> sumMap;
  map<int, int>::iterator it;
  int sum = 0;
  for (int i = 0; i < arr.size(); i++) 
  {
    sum += arr[i];
    it = sumMap.find(sum);
    if (it != sumMap.end()) 
    {
        return make_pair(it->second + 1, i);
    } else {
        sumMap.insert(make_pair(sum, i));
  }
}

int main()
{
  int arr[] = {1,4,-3,-4,6,-7,8,-5};
  vector<int> input(arr, arr + sizeof(arr) / sizeof(arr[0]));
  pair<int, int> result = FindSubsequenceSum(input);

  cout << "(" << result.first << "," << result.second << ")" << endl;

  return 0;
}

Output:
(2,6)