未排序正数数组中累加和为给定值的最长子数组长度

题目

给定一个数组 arr，该数组无序，但每个值均为正数，再给定一个正数 k。求 arr 的所有子数组中所有元素相加和为 k 的最长子数组长度。例如，arr = [1，2，1，1，1]，k = 3。累加和为3的最长子数组为 [1，1，1]，所以结果返回 3。

解答

这道题可以使用暴力求解的方法，直接来一个双循环即可，问题是，这显然不是好的解决方案。所以，我们需要借助双指针来求解。这里，我们使用 left 和 right 分别来代替左指针和右指针。用 sum 来代表从 arr[left] 到 arr[right] 的累加值。

首先，它们的起始位置都是 0 这个索引，然后，移动的规则是：

  • 1、如果 sum < k，那么，right 指针向右移动一格。这一步很好理解，我们在作暴力破解时，第二层循环也是这么做的，这里 right 指针的作用就相当于暴力破解的第二层循环。

  • 2、如果 sum == k，那么，left 指针向右移动一格。类比暴力破解，这里就相当于 left 对应的在第二层循环中 right 指针后面的元素都直接被跳过了。为什么可以这样呢？原因就在于如果 right 指针向右移动的话，那么，这些所有被跳过的元素都是不符合情况的，因为无论怎么移动都会使得 sum 比 k 要大。所以只好是 left 指针向右移动一格了，这就相当于暴力循环中的第一层循环的索引加一。

  • 3、如果 sum > k，那么，left 指针向右移动一格。这样做的原因是 right 指针后面的元素都不符合要求。那么，还有一个问题，就是我们 left 向右移动完一格之后，我们可以注意到，当前的 left 到 right 之间的元素都被跳过了（类比于暴力破解的话），为什么可以这样呢？这也是同样的道理，在当前 left 的情况下，无论 right 指向哪些被跳过元素中的哪一个，都是不合要求的，它们都会使 sum 小于 k。

我们按照上面的规则，不断地进行移动，直到 right 指针到达了右边界为止。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public int getMaxLength(int[] arr, int k) {
    if (arr == null || arr.length == 0 || k <= 0) {
        return 0;
    }
    int left = 0;
    int right = 0;
    int sum = arr[0];
    int len = 0;
    while (right < arr.length) {
        if (sum == k) { // 等于 k 的情况，左指针向右移动格，因为 right 右面的情况已经可以全部排除
            len = Math.max(len, right - left + 1);
            sum -= arr[left++];
        } else if (sum < k) { // 小于 k 的情况，右指针向右移动一格，如果 right 到达了尽头，则说明接下来的所有情况都不符合，直接跳出循环即可
            right++;
            if (right == arr.length) {
                break;
            }
            sum += arr[right];
        } else { // sum > k 的情况
            sum -= arr[left--];
        }
    }
    return len;
}

测试

1
2
3
4
5
6
public static void main(String[] args) {
    int[] arr = {1, 2, 1, 1, 1};
    GetSubArrMaxLen_9 gsaml = new GetSubArrMaxLen_9();
    int res = gsaml.getMaxLength(arr, 3);
    System.out.println(res);
}

输出

3