java - 如何在 O(n) 时间复杂度内找到和为 k 的所有子数组？

Question

我可以使用以下代码搜索总和为 k 的子数组:

public static void subarraySum(int[] arr, int sum) {

    int start=0;
    int currSum=arr[0];

    for(int i = 1;i<=arr.length;i++) {
        while(currSum>sum ) {
            currSum-=arr[start];
            start++;
        }
        if(currSum==sum) {
            System.out.println(start + " " + (i-1) + " index");
            start=i;
            currSum=0;
        }
        if(i<arr.length) {
            currSum +=arr[i];
        }

    }

这适用于像 {15,2,4,8,9,5,10,23} 这样的数组。此输出将是 2 个子数组 {2,4,9,8} 和 {23}。

但是，对于像 {1,5,2,5,1,3} 这样的数组，这只会给我输出 1 个子数组，但是有 2 个子数组总和为 7，分别是 {5,2} 和 {2, 5}。关于如何调整上述代码以在第二个数组中给出正确答案的任何建议？

Answer 1

算法并不复杂，我会讲解思路，实现留给大家自己去尝试。

你需要有两个索引i, j。让它们都从第一个元素开始。现在获取它们之间的子数组(最初因为它们都在同一个地方没有子数组)并进行以下测试:

• 如果总和等于您的目标，则添加当前子数组

• 如果总和小于你的目标，将 j 移到右边以包含一个更多元素再做测试

• 如果总和大于您的目标，将 i 移到右边以移除子数组中的第一个元素，然后再次进行测试。

最后，您将拥有总和等于目标的所有子数组。

please note that this solution only works for positive numbers