算法: 和等于target的最长子数组

给定一个数组arr,其中可能有正、有负、有0，给定一个整数target,返回arr中所有子数组里，累加和等于target的子数组长度最大是多少?

思路:
最简单直观的思路就是暴力，两个for循环，枚举所有子数组，看和是否等于target,如果等于就记下长度，找出最长就可以了。这样的时间复杂度是O(n^2)。使用前缀和的方法可以使时间复杂度到O(n)。做法是遍历数组，走到下标 i ，计算从0到 i 的和sum，并且记住这个和sum和i，同时看记忆中是否有 sum-target 的记录，如果有记录并且记录的下标为i'，则代表找到一个子数组[i',i]满足和等于target。

代码:

int maxLength(vector<int> &arr, int target) {
    if (arr.size() == 0) {
        return 0;
    }
    unordered_map<int, int> map;
    map.insert({0,-1});
    int sum = 0;
    int ans = 0;
    for(int i = 0;i < arr.size();i++) {
        sum += arr[i];
        if (map.find(sum - target) != map.end()) {
            ans = max(ans,i - map.at(sum-target));
        }
        if (map.find(sum) == map.end()) {
            map.insert(make_pair(sum, i));
        }
    }
    return ans;
}