325. Maximum Size Subarray Sum Equals k (1)

Link

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。

需要一個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);
      }
   }
   
}