Leetcode 325: Maximum Size Subarray Sum Equals K

https://leetcode.com › problems › maximum-size-subarray-sum-equals-k

Notes:

This question can be a very good interview question due to the follow up. The basic idea is that using a hash table to record the index when one unique sum shows up.

if sum[i to j] = sum[0 to j] - sum[0 to i-1] = k, then we just need to check whether (sum[0 to j] - k) is already observed or not, which is sum[0 to i-1]. Thus, we can run this in O(N).

See the code below:

class Solution {
public:
    int maxSubArrayLen(vector<int> &nums, int k) {
        int res = 0, sum = 0;
        unordered_map<int, int> mp;
        for(int i=0; i<nums.size(); ++i) {
            sum += nums[i];
            if(sum == k) res = max(res, i + 1);
            else if (mp.count(sum-k)) res = max(res, i - mp[sum-k]);
            if(!mp.count(sum)) mp[sum] = i;
        }
        return res;
    }
};