Maximum Size Subarray Sum Equals k

• medium
• tag: hashmap, preSum
• similar: continuous array sum

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.

• eg : 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)

思路

• 既然是连续的subarray sum, 自然就是preSum array, 然后任意一段subarray的和(例如sum[i~j] = preSum[j] - preSum[i-1]). 我的想法就是loop一遍建立preSum, 同时建立map(从而是O(1)的找到对应的preSum的index). 注意, 这里因为有个dummy preSum, 即index = -1的时候, preSum = 0. 所以我选择了0base的, 然后len的部分有点混乱: 减还是不减1?
  • 这种思路不但需要O(N)的空间存preSum array
  • 还要是2-pass的时间.

idea 0

• 我的解法
• 代码如下

public int maxSubArrayLenBAD(int[] nums, int k) {
    if (nums == null || nums.length == 0)  return 0;
    int[] preSum = new int[nums.length+1];
    Map<Integer, Integer> map = new HashMap<>();

    //map.put(0, -1);
    for (int i = 0; i < nums.length; ++i) {
      preSum[i+1] = preSum[i] + nums[i];
      map.put(preSum[i+1], i+1);
    }
    int ret = 0;
    for (int i = 1; i < nums.length + 1; ++i) {
      if (!map.containsKey(k+preSum[i-1]))  continue;
      int indJ = map.get(k+preSum[i-1]);
      int len = indJ - i + 1;
      ret = Math.max(ret, len);
    }
    return ret;
}

idea 1

• 参考的discuss里面的1-pass解法, link
• 思路和我的类似, 也是在hashmap里面找sum-k的index, 但就是写得好. 我修改了一下, 即使用virtual preSum: 0存在-1的位置. 这在array, list, graph里面经常使用, 统一解决边界问题.
• 代码如下, 注意sum只存1次, 因为是找max length, 所以是最远距离, 所以保存第一次出现的位置.

public int maxSubArrayLen(int[] nums, int k) {
    int sum = 0, max = 0;
    HashMap<Integer, Integer> map = new HashMap<>();
    map.put(0,-1);
    for (int i = 0; i < nums.length; i++) {
      sum = sum + nums[i];
      //if (sum == k) max = i + 1;
      if (map.containsKey(sum - k))
        max = Math.max(max, i - map.get(sum - k));
      if (!map.containsKey(sum)) map.put(sum, i);
    }
    return max;
}