Maximum Size Subarray Sum Equals k

LeetCode #325

Description:

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.

Note: The sum of the entire nums array is guaranteed to fit within the 32-bit signed integer range.

Example:

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)

Idea:

用hash table存下每个sum对应的index（如果已经存在就不用了），然后看sum-k存在于hash table不，如果存在，就计算长度，并与max len对比。

Time: O(n);

Code:

class Solution {
public:
    int maxSubArrayLen(vector<int>& nums, int k) {
        unordered_map<int, int> hash_tb;
        hash_tb[0]=-1;

        int max_len=0;
        int sum=0;
        for(int i=0; i<nums.size(); ++i){
            sum += nums[i];

            if(hash_tb.find(sum-k)!=hash_tb.end()){
                max_len = max(max_len, i-hash_tb[sum-k]);
            }

            if(hash_tb.find(sum)==hash_tb.end()){
                hash_tb[sum]=i;
            }
        }

        return max_len;
    }
};