算法刷题目数组和矩阵
Source
Edit
History

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

一、题目

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

1
arr = [3, -2, -4, 0, 6]，k = -2，相加和小于或等于-2的最长子数组为[3, -2, -4, 0]，所以结果返回4。
  • 如果要返回最长子数组的左右下标呢？
  • 如果给定的数组是循环的，即最后一个元素和第一个元素可以做为相邻元素

二、分析

这种类型的题目和 “未排序数组中累加和等于给定值的最长子数组的问题” 是相同的问题，我们在 “和为给定值” 的问题中，得到了如下的公式：

1
2
3
我们假定 s(i) 为 sum，sum-k 为 s(j)
那么 k = sum - (sum-k) = s(i) - s(j) = arr[j+1 ... i]
也就是说数组中下标从 j+1 到 i 位置的子数组的累加和为 k

我们之前是这样做的，有一个变量 sum 作为 arr[0 ... i] 子数组的累加和。有一个 map ，key 记录 sum 值，value 记录当为 sum 时，第一次出现在数组中的位置。

那我们在本题中，我们需要得到累加和小于等于 K，我们没法用 map 了，map 只能找到一个固定值，而现在我们需要找到一组数据，也就是一组大于或等于 sum-k 的值。

我们想要求累加和小于等于 K 的数据，只需要求出第一个大于或等于 sum-k 的位置即可。因为我们只关心第一个大于 sum-k 的位置，如果累加和为 2 已经大于 sum-k，那么累加和 3 必定大于 sum-k，所以只要保留一个更大的、出现更早的累加和即可。

再解释下，如果从 0 位置到 j 位置累加和为 sum[0..j]，此时想求以 j 位置结尾的累加和小于等于 K 的最长子数组长度。那么只需要知道大于或等于 sum[0..j]-K 这个值的累加和最早出现在 j 之前的什么位置即可。假设那个位置是 i 位置，那么 arr[i+1,j] 就是 j 位置结尾的累加和小于等于 K 的最长子数组。

由于不是具体值，而是范围值，所以不能使用 hashmap。因此我们使用一个辅助数组 helpArr 。

  • 首先生成 arr 每个位置从左到右的累加和数组 sumArr。以 [1, 2, -1, 5, -2] 为例，生成的 sumArr=[0, 1, 3, 2, 7, 5]。注意，sumArr 中第一个数为 0，表示当没有任何一个数时的累加和为 0。
  • 生成 sumArr 的左侧最大值数组 helpArr，sumArr={0,1,3,2,7,5} => {0,1,3,3,7,7}。因为我们只关心大于或等于某个值的累加和最早出现的位置，而累加和 3 出现在 2 之前，并且大于或等于 3 必然大于 2，所以当前保留一个更大的，出现更早的累加和即可
  • helpArr 是 sumArr 每个位置上的左侧最大值数组，那么他当然是有序的，在这样一个有序的数组中，就可以二分查找大于或等于某一个值的累加和最早出现的位置。例如，在[0,1,3,3,7,7]中查找大于或等于4这个值的位置，就是第一个7的位置
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
42
class Solution {
public:
    int get_max_len(const std::vector<int>& arr, int k) {
        std::vector<int> help_arr(arr.size()+1, 0);
        int sum = 0;
        // 没有任何一个数时的累加和为 0
        help_arr[0] = 0;
        for (int i = 0; i < arr.size(); i++) {
            sum += arr[i];
            help_arr[i+1] = std::max(sum, help_arr[i]);
        }
        sum = 0;
        int res = 0;
        int pre = 0;
        int len = 0;
        for (int i = 0; i < arr.size(); i++) {
            sum += arr[i];
            pre = get_less_index(help_arr, sum-k);
            len = pre == -1 ? 0 : i-pre+1;
            res = std::max(res, len);
        }
        return res;
    }

private:
    int get_less_index(const std::vector<int>& arr, int num) {
        int low = 0;
        int high = arr.size() - 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;
    }
};

现在加两个条件，一个条件是返回左右下标，另一个条件是这个数组如果是一个循环数组。返回左右下标好办，只需要增加两个变量来保存即可。但是循环数组这个条件较为麻烦。

我们之前的做法在求 sum 的时候，都是从 0 开始的，一直到数组的末尾结束。如果是循环数组的话，需要以任何位置为起点，终点为起点的前一个位置，也就是说，如果我们的数组为 [3,2,5,1]，则需要求这些数组：

1
2
3
4
[3,2,5,1]
[2,5,1,3]
[5,1,3,2]
[1,3,2,5]

这样，可以以任何位置为起点，也就是达到了循环数组的目的。

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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
class Solution2 {
public:
    std::pair<int, int> get_cycle_arr_max_len(const std::vector<int>& arr, int k) {
        int left = 0, right = 0;
        int len = 0;
        for (int i = 0; i < arr.size(); i++) {
            std::vector<int> tmp_arr;
            int end = i == 0 ? arr.size()-1 : i-1;
            for (int j = i; j != end; j++, j%=arr.size()) {
                tmp_arr.emplace_back(arr[j]);
            }
            tmp_arr.emplace_back(arr[end]);
            print_arr(tmp_arr);
            auto res = get_max_len(tmp_arr, k);
            if (res.second - res.first + 1 > len) {
                len = res.second - res.first + 1;
                left = res.first+i >= arr.size() ? (res.first+i)%arr.size() : res.first+i;
                right = res.second+i >= arr.size() ? (res.second+i)%arr.size() : res.second+i;
            }
        }
        return std::pair<int, int>(left, right);
    }

private:
    std::pair<int, int> get_max_len(const std::vector<int>& arr, int k) {
        std::vector<int> help_arr(arr.size()+1, 0);
        int sum = 0;
        // 没有任何一个数时的累加和为 0
        help_arr[0] = 0;
        for (int i = 0; i < arr.size(); i++) {
            sum += arr[i];
            help_arr[i+1] = std::max(sum, help_arr[i]);
        }
        sum = 0;
        int res = 0;
        int pre = 0;
        int len = 0;
        int left = 0, right = 0;
        for (int i = 0; i < arr.size(); i++) {
            sum += arr[i];
            pre = get_less_index(help_arr, sum-k);
            len = pre == -1 ? 0 : i-pre+1;
            if (len > res) {
                left = pre;
                right = i;
                res = len;
            }
        }
        return std::pair<int, int>(left, right);
    }

    int get_less_index(const std::vector<int>& arr, int num) {
        int low = 0;
        int high = arr.size() - 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;
    }

    void print_arr(const std::vector<int>& arr) {
        for (const auto& x : arr) {
            std::cout << x << " ";
        }
        std::cout << std::endl;
    }
};