# 325. Maximum Size Subarray Sum Equals k (1)

[Link](https://www.cnblogs.com/grandyang/p/5336668.html)

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.

**Note:**\
The sum of the entire nums array is guaranteed to fit within the 32-bit signed integer range.

**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**

觀察到可以透過到currentSum(假設目前在index i) - previousSum(假設在index j) = k 的方式來判斷(i, j)之間的sum是k。

那麼只要找到滿足條件的j-i的最大值，就可以求解。

那問題在於怎麼找到j。&#x20;

需要一個Data structure去紀錄每個sum並記錄出現時最小的index比較方便尋找。 要記錄的東西有兩個且之間有關聯性。hashMap為佳。 又因為查找的對象是sum值(滿足(Sum\_Of\_i)-K == sum)。

所以sum值當key, 最小index當value。

```
public int maxSubArrayLen(int[] nums, int k) {
   int len = nums.length;
   int sum = 0;
   //用hashmap紀錄 到每個index為止的最大sum值，還有其對小的index
   HashMap<int, int> map = new HashMap<>();
   int ans = 0;
   for(int i = 0; i < len; i++){
      sum = sum + nums[i];
      if(sum == k){
         ans = i + 1;
      }
      //這裡用else，是因為若滿足sum == k 就表示0~i一定是目前最長，不用再另外check其他可能
      else if(map.contains(sum-k)){
         ans = Math.max(ans, i - map.get(sum-k));
      }
      //只記錄最小的index
      if(!map.contains(sum)){
         map.put(sum, i);
      }
   }
   
} 
```
