未排序数组中累加和小于或等于给定值的最长子数组长度

题目

给定一个无序数组 arr，其中元素可正、可负、可 0。给定一个整数 k，求 arr 所有的子数组中累加和小于或等于 k 的最长子数组长度。

例如：arr = [3, -2, -4, 0, 6]，k = -2，相加和小于或等于 -2 的最长子数组为 {3, -2, -4, 0}，所以结果返回 4。

要求：时间复杂度为 \(O(N)\)。

解答

首先是 \(O(NlogN)\) 时间复杂度的解法，这个解法和之前的求解未排序数组中累加和为给定值的最长数组系列问题类似。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
// 时间复杂度为 O(NlogN)，额外空间复杂度为 O(N)
public int maxLength(int[] arr, int k) {
    int[] helpArr = new int[arr.length + 1]; // 辅助数组
    int sum = 0;
    helpArr[0] = sum; // 第一个元素为 0，表示当没有任何数时的累加和为 0
    for (int i = 0; i != arr.length; i++) {
        sum += arr[i];
        helpArr[i + 1] = Math.max(sum, helpArr[i]);
    }
    sum = 0;
    int res = 0;
    int pre = 0;
    int len = 0;
    for (int i = 0; i != arr.length; i++) {
        sum += arr[i];
        // 最关键之处
        // 找到 helpArr 中大于等于 sum - k 第一次出现的位置，
        // 这个位置等价于以 i 为结尾位置的长度最长的符合要求的子数组
        pre = getLessIndex(helpArr, sum - k);
        len = pre == -1 ? 0 : i - pre + 1;
        res = Math.max(res, len);
    }
    return res;
}
// 二分查找，查找 arr 数组中第一次出现的大于等于 num 的索引位置，如果没找到，则返回 -1
public int getLessIndex(int[] arr, int num) {
    int low = 0;
    int high = arr.length - 1;
    int mid = 0;
    int res = -1;
    while (low <= high) {
        mid = low + (high - low) / 2;
        if (arr[mid] >= num) {
            res = mid;
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }
    return res;
}

完美的 \(O(N)\) 的解法，这种解法也可以看成是 “滑动窗口” 的应用。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
// 时间复杂度为 O(N) 的解法，额外空间复杂度为 O(N) 的解法
public int maxLengthAwesome(int[] arr, int k) {
    if (arr == null || arr.length == 0) {
        return 0;
    }
    int[] minSums = new int[arr.length]; // minSums[i] 表示必须以 arr[i] 开头的所有子数组中，能
    int[] minSumEnds = new int[arr.length]; // minSumEnds[i] 表示得到了最小累加和的子数组的右边界
    minSums[arr.length - 1] = arr[arr.length - 1];
    minSumEnds[arr.length - 1] = arr.length - 1;
    // 从右向左遍历，填充 minSums 和 minSumEnds 的值
    for (int i = arr.length - 2; i >= 0 ; i--) {
        if (minSums[i + 1] <= 0) { // 如果 i 的右面的元素的最小累加和小于等于 0（原书这里没有等于号，但是加上等于号
            minSums[i] = arr[i] + minSums[i + 1];
            minSumEnds[i] = minSumEnds[i + 1];
        } else {
            minSums[i] = arr[i];
            minSumEnds[i] = i;
        }
    }
    int end = 0;
    int sum = 0;
    int res = 0;
    // i 是窗口的最左位置，end 是窗口最右位置的下一个位置
    for (int i = 0; i < arr.length; i++) {
        // 如果 end 没有越界，且当前子数组还可以继续往右扩
        while (end < arr.length && sum + minSums[end] <= k) {
            sum += minSums[end];
            end = minSumEnds[end] + 1;
        }
        res = Math.max(res, end - i);
        if (end > i) { // 窗口内还有数
            sum -= arr[i];
        } else { // 窗口已经没有数了，说明从 i 开头的所有子数组累加和都不可能小于或等于 k
            end = i + 1;
        }
    }
    return res;
}

测试

1
2
3
4
5
6
7
8
public static void main(String[] args) {
    int[] arr = {0, 2, 5, 3, 2, -2, 1, -1};
    int k = 3;
    // 测试
    GetMaxLengthAwesome_11 gmla = new GetMaxLengthAwesome_11();
    System.out.println(gmla.maxLengthAwesome(arr, k));
    System.out.println(gmla.maxLength(arr, k));
}

输出

5
5