Given an array nums and a target value k, find the maximum length of a subarray that sums to k. If there isn't one, return 0 instead.

Example 1:
Given nums = [1, -1, 5, -2, 3], k = 3,
return 4. (because the subarray [1, -1, 5, -2] sums to 3 and is the longest)

Example 2:
Given nums = [-2, -1, 2, 1], k = 1,
return 2. (because the subarray [-1, 2] sums to 1 and is the longest)

Follow Up:
Can you do it in O(n) time?

算法

先定義s的概念
s(i)代表子數(shù)組arr[0..i]中所有元素的累加和.
那么, arr[j..i] (0<=j<=i<=arr.length-1)的累加和為s(i) - s(j-1).

變量
sum = 0, 表示從arr[0]開始一直到arr[i]的子數(shù)組累加和.
len = 0, 表示累加和為k的最長(zhǎng)子數(shù)組長(zhǎng)度.

設(shè)置哈希表
key: 表示出現(xiàn)過(guò)的累加和sum
value: 表示某個(gè)累加和sum值出現(xiàn)時(shí), 最早的位置 i.

• 遍歷數(shù)組 *
  以遍歷到當(dāng)前元素為arr[i]為例.

1. 此時(shí)累加和為sum = sum + arr[i], 查看哈希表中是否存在key為sum - k的記錄.
2. 如果哈希表中存在sum-k, 則取出對(duì)應(yīng)的value, 記為j. 那么 arr[j+1, i]的累加和為s[i] - s[j] = sum - (sum -k) = k. 因?yàn)閖是累加和為sum-k最早出現(xiàn)的位置, 所以arr[j+1..i]是以arr[i]結(jié)尾的, 累加和為k的最長(zhǎng)子數(shù)組. 如果 i - j 大于len, 則更新len.
3. 如果哈希表中不存在value為sum-k的記錄, 繼續(xù)步驟2.
4. 如果哈希表中不存在累加和為sum的記錄, 將記錄<sum, i>插入到哈希表中
5. 繼續(xù)遍歷下一個(gè)元素, 直到所有元素遍歷完.

• 邊界條件*
  對(duì)于 arr[0..i] 的累加和, 可以表示為 s(i) - s(-1), 即累加和為0的最早出現(xiàn)的位置為-1.

實(shí)現(xiàn)

int maxSubarraySumK(std::vector<int>& nums, int target)
{   
    if (nums.size() == 0)
    {   
        return 0;
    }   
    int maxLen = 0;
    std::map<int, int> sum2IndexMap;
    sum2IndexMap[0] = -1; 
    int sum = 0;
    for (int i = 0; i < nums.size(); ++i)
    {   
        sum = sum + nums[i];
        auto iter = sum2IndexMap.find(sum - target);
        if (iter != sum2IndexMap.end())
        {   
            maxLen = std::max(i - iter->second, maxLen);
        }
        if (sum2IndexMap.find(sum) == sum2IndexMap.end())
        {
            sum2IndexMap.insert(std::make_pair(sum, i));
        }
    }
    return maxLen;
}

};