未排序数组中累加和为给定值的最长子数组系列问题

一、题目

给定一个无序数组 arr，其中元素可正、可负、可 0。给定一个整数 k，求 arr 所有的子数组中累加和为 k 的最长子数组长度
给定一个无序数组 arr，其中元素可正、可负、可 0。求 arr 所有的子数组中正数与负数个数相等的最长子数组长度
给定一个无序数组 arr，其中元素只是 1 和 0。求 arr 所有子数组中 0 和 1 个数相等的最长子数组长度

问题 2 和问题 3 都可以转换为问题 1
问题 2 可以把数组中正数、负数转换为 1 和 -1，然后求累加和为 0 的最长子数组长度
问题 3 可以把数组中的 0 转换为 -1，然后求累加和为 0 的最长子数组长度

二、思路

对于这三道题，是同样的套路，我们先推演一个公式

s(i) = arr[0 ... i]
s(j) = arr[0 ... j]  假定 j < i
s(i) - s(j) = arr[0 ... i] - arr[0 ... j] = arr[j+1 ... i]
也即 s(i) - s(j-1) = arr[j ... i]

有了这个公式，我们就可以来解决问题了。

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 时，第一次出现在数组中的位置。最后一个变量 len 记录最长的子数组长度。

遍历这个数组，每次先给 sum 值加上 arr[i]。然后从 map 中寻找是否存在 sum-k，如果存在，说明有和为 k 的子数组，并且这个子数组的下标是从 j+1 到 i 位置；更新 len 即可。然后在判断 map 中是否存在 sum ，如果不存在，则添加 (sum, i)。如果存在，则不用管，因为我们只保存第一次出现在数组中的位置。

遍历结束，返回 len 即可。

三、代码

#include <vector>
#include <unordered_map>
#include <iostream>

class Solution {
public:
    int get_max_subarr(const std::vector<int>& arr, int k) {
        if (arr.empty()) {
            return 0;
        }
        // 表示当前范围内数组的累加和
        int sum = 0;
        // map 的 key 为 sum 值，value 表示第一次出现 sum 值的位置
        std::unordered_map<int, int> mp;
        mp[0] = -1;
        int len = 0;
        for (int i = 0; i < arr.size(); ++i) {
            sum += arr[i];
            auto iter = mp.find(sum-k);
            if (iter != mp.end()) {
                len = std::max(len, i - iter->second);
            }
            if (mp.find(sum) == mp.end()) {
                mp[sum] = i;
            }
        }
        return len;
    }
};

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