# 325 Maximum Size Subarray Sum Equals k

input是一個int array和int k，回傳加總為k的subarray的最長長度。

• idea

  1. 最簡單的想法就是brute force，O(N^2)
  2. 這個題目最快應該可以用O(N)來解出，也就是跑過一遍矩陣就得到答案。最初的想法覺得可以把累加的總和存起來:

    input = [1,-1,5,-2,3]
    sum = [1,0,5,3,6]
  

  那假如k=3，[1,-1,5,-2]就是最長的subarray，答案可以在sum裡面找到。

    input = [-1,-2,3,1]
    sum = [-1,-3,0,1]
  

  假如k=1，[-2,3]是最長的subarray，而最長長度可以由sum得到

    desired sum = 0-(-1) = (-1+(-2)+3) - (-1) = 1
    length = index(0)-index(-1) = 2 - 0 = 2
  

  但是要在sum裡搜尋相減等於k的pair就又要花n^2時間了，所以可以用hashmap讓搜尋變成O(1)
  整理一下現在的idea: use a hashmap to save (sum, index) pair. variable sum to keep track of cumulative sum. variable max to keep track of the length of the longest subarray.

• pseudocode:

  for each element in nums,
      sum += current element
      if sum == k, max = i
      if map.containsKey(sum - k) max = i-map.get(sum-k)
      else map.put(sum, i)
  

• code:

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

  如果想更加速，可以再減少map access。