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

一、题目

给定一个数组 arr，该数组无序，但每个值均为正数，再给定一个正数 k，求 arr 的所有子数组中所有元素相加和为 k 的最长子数组长度

1 2	例如，arr = [1, 2, 1, 1, 1], k = 3 累加和为 3 的最长子数组为 [1, 1, 1], 所以结果返回 3

二、思路

数组中全部为正数，我们有如下几个变量，len 初始为 0，表示子数组的长度。left 初始为 0，表示子数组的左边界，right 初始为 0，表示子数组的右边界。 sum 初始值为 arr[0]，表示 arr[left ... right] 之间求和。

我们开始遍历，条件是 right < arr.size() 。

当 sum 值等于 k 时，说明此时 left 和 right 之间的子数组累加和等于给定值了，更新一下 len 的值。由于数组中都为正数，以 left 为左边界，right 右边的所有子数组都不满足条件了。所以此时给 left++，自增之前注意 sum 减去 left 处的值。
当 sum 值大于 k 时，同样的，需要给 left++，加之前注意 sum 减去 left 处的值
当 sum 值小于 k 时，需要给 right++，right 自增之前先让 sum 加上 right 处的值。此时注意 right 不能越界。

注意，我们的 sum 维护的是 arr[left ... right] 之间的求和。

三、代码

#include <vector>
#include <iostream>

class Solution {
public:
    int get_max_length(const std::vector<int>& arr, int k) {
        if (arr.empty()) {
            return 0;
        }
        int left = 0, right = 0;
        int sum = arr[0];
        int len = 0;
        for (; right < arr.size();) {
            if (sum == k) {
                len = std::max(len, right-left+1);
                sum -= arr[left++];
            } else if (sum < k) {
                right++;
                if (right < arr.size()) {
                    sum += arr[right];
                } else {
                    break;
                }
            } else {
                sum -= arr[left++];
            }
        }
        return len;
    }
};

int main() {
    Solution s;
    std::vector<int> arr{1, 9, 1, 2, 3};
    int res = s.get_max_length(arr, 5);
    std::cout << res << std::endl;
    return 0;
}