LeetCode Q325: Maximum Size Subarray Sum Equals k

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?

Solution:

This question remind me of using range sum which require you preprocessing the array and you can get sum of any range in constant time.

Once we preprocess the array, for each location given its range sum starting from 0, to quickly find the part with remaining sum, we should use hash table with range sum as key and array index as content.

	class Solution {
	public:
	int maxSubArrayLen(vector<int>& nums, int k) {
	if(nums.empty())
	return 0;
	unordered_map<int, int> myMap;
	myMap[nums[0]]=0;
	myMap[0]=-1;
	for(int i=1; i<nums.size(); i++){
	nums[i]=nums[i-1]+nums[i];
	auto it = myMap.find(nums[i]);
	if(it==myMap.end())
	myMap[nums[i]]=i;
	}
	int maxv=INT_MIN;
	for(int i=0; i<nums.size(); i++){
	auto it = myMap.find(nums[i]-k);
	if(it==myMap.end())
	continue;
	if(it->second<i)
	maxv=max(maxv, i-myMap[nums[i]-k]);
	}
	return maxv==INT_MIN? 0:maxv;
	}
	};

view raw Q325.cpp hosted with ❤ by GitHub