[Summary] Subarray sum

[LC 209]. Minimum Size Subarray Sum: Given an array of n positive integers and a positive integer s, find the minimal length of a subarray of which the sum ≥ s. If there isn’t one, return 0 instead. Example: given the array [2,3,1,2,4,3] and s = 7, return 2, [4, 3].

[LC 325]. 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: Given nums = [1, -1, 5, -2, 3], k = 3, return 4, [1, -1, 5, -2]

第一题保证所有numbers是positive,所以可以用sliding window解决。第二题不保证所有数字都是positive,可以用一个经典思路,类似DP。只要是求一整个sequence中有哪个sub-sequence的sum满足一定条件,都可以考虑以下思路:i=0 to n-1,算0 to i的sum,存在array或map中,当前sum for [0, i]减去之前某个sum for [0, j],即得到[j, i]范围内的sum,是否符合target的要求。用同样思路的还有[LC 303]. Range Sum Query – Immutable 和 [LC 304]. Range Sum Query 2D – Immutable.

先说第一题:只需判断当前window内的sum和target比是大还是小。

int len = Integer.MAX_VALUE;
int start = 0, end = 0, sum = nums[start];
while (start <= end) {
     if (sum < s) { // sum smaller than target, expand the window 
         end++;                 
         if (end >= nums.length) break;
         sum += nums[end];
         if (end-start+1 > len) { // optimization, if current window is already larger than the smallest, then no need to check it, shrink the window anyway
                sum -= nums[start];
                start++;
          }
     } else if (sum >= s) { // sum larger than target, meet the requirement, remember the current length of the window/subarray, shrink the window to further search for other windows that meet the requirement
         len = Math.min(len, end-start+1);
         sum -= nums[start];
         start++;
     } 

}
if (len == Integer.MAX_VALUE) return 0; // if "len" is neven hit, than such subarray does not exist
return len;

再说第二题:需要一遍记录0到i的sum,一遍寻找之前是否有某个0到j的sum满足sum_i – sum_j == target

        Map map = new HashMap();
        int sum = 0;
        int len = 0;
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i]; // accumulated sum from 0 to i
            if (!map.containsKey(sum)) {
                map.put(sum, i); // map stores the earliest location of a value for sum, so that later max subarray length can be obtained
            } 
            if (sum == k) {
                len = i+1; // meaning subarray 0 to i has the target sum, this is guaranteed to be the longest subarray until now
            } else if (map.containsKey(sum - k)) { // see if can find a sum for [0, j], so that sum for [0, i] - sum for [0, j] meets the target 
                len = Math.max(len, i - map.get(sum - k));
            }
        }
        return len;
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s