algorithm - 查找相等和的连续子数组

Question

Given array : 8 3 5 2 10 6 7 9 5 2
So the o/p will be Yes.   

如:{8,3,5} {10,6} {9,5,2} 它们都具有相同的总和值，即 16。

But for this array : 1 4 9 6 2 12
      o/p will be No.

因为:没有连续的幻灯片具有相同的总和值

我曾考虑使用 SubSetSum 算法/Kadane 最大子数组算法，但后来我最终决定使用，因为所有算法都需要一个预定义的目标总和。 但是这里我们不知道目标总和

Answer 1

如果给出了所需的总和，并且所有子数组应该是连续的，那么可以在 O(n) 中轻松完成。

在数组上运行一个循环并维护切片的边界(left 和 right 索引)和 currentSum。

以第一个元素作为 0 开始。边界将为 [0, 0](为简单起见，我们包括右)。然后在一个循环中你有三个条件。

1. 如果和小于期望值，则将右元素添加到和并推进右索引
2. 如果总和大于期望值，则从总和中移除左边的元素并推进左边的索引
3. 如果总和等于给定，打印切片。为了在下一次迭代中避免这个切片，推进左索引并调整总和。

翻译成代码

    public static void main(String[] args) {
        int givenSum = 16;
        int[] a = new int[] {8, 3, 5, 2, 10, 6, 7, 9, 5, 2};

        // boundaries of slice
        int left = 0; // defines position of slice
        int right = 0; // exclusive
        int currentSum = 0;

        while (right < a.length) {

            if (currentSum < givenSum) { // sum is not enough, add from the right
                currentSum += a[right];
                right++;
            }

            if (currentSum > givenSum) { // sum exceeds given, remove from the left
                currentSum -= a[left];
                left++;
            }

            if (currentSum == givenSum) { // boundaries of given sum found, print it
                System.out.println(Arrays.toString(Arrays.copyOfRange(a, left, right)));
                // remove the left element, so we can process next sums
                currentSum -= a[left];
                left++;
            }
        }

    }

对于你的情况，它打印 4 个切片，产生总和 16

[8, 3, 5]
[10, 6]
[7, 9]
[9, 5, 2]

编辑:

正如 OP 所阐明的，没有可用的给定总和，目标是检查是否存在至少两个不同的连续子数组，它们产生的总和相等。

最直接的算法是生成所有可能的和并检查是否有重复

int[] a = new int[] {1, 4, 9, 6, 2, 12};

HashSet<Integer> sums = new HashSet<>();
int numOfSums = 0;

for (int left = 0; left < a.length - 1; left++) {
    for (int right = left; right < a.length; right++) {
        // sum from left to right
        int sum = 0;
        for (int k = left; k <= right; k++) {
            sum += a[k];
        }
        numOfSums++;
        sums.add(sum);
    }
}
System.out.println(sums.size() == numOfSums);

这个的复杂度是 O(n^3)，不是很好，但是有效。

提示:可以探索一个技巧将其提升到 O(n^2)，您不需要为每一对切片计算总和!