325. Maximum Size Subarray Sum Equals k

Given an integer array nums and an integer k, return the maximum length of a

subarray

that sums to k. If there is not one, return 0 instead.

Example 1:

Input: nums = [1,-1,5,-2,3], k = 3
Output: 4
Explanation: The subarray [1, -1, 5, -2] sums to 3 and is the longest.

Example 2:

Input: nums = [-2,-1,2,1], k = 1
Output: 2
Explanation: The subarray [-1, 2] sums to 1 and is the longest.

Constraints:

• 1 <= nums.length <= 2 * 105
• -104 <= nums[i] <= 104
• -109 <= k <= 109

Solution:

class Solution {
    public int maxSubArrayLen(int[] nums, int k) {
        // 哈希表用来存储前缀和以及它第一次出现的位置索引
        Map<Integer, Integer> prefixSumMap = new HashMap<>();
        // prefixSumMap: <0, -1> <-2, 0> <-3,1> <-1,2>
        // 

        int maxLen = 0; // 记录最长子数组的长度
        int prefixSum = 0;  // 当前的前缀和

        prefixSumMap.put(0, -1);
        // 初始化前缀和为0, 位置为-1, 表示在数组开始之前
        // [-2, -1, 2, 1]
        //          i 
        for (int i = 0; i < nums.length; i++){
            prefixSum = prefixSum + nums[i]; // prefixSum = 0 - 2= -2
            // ---
          /// -2 -1 = -3  
          // -3 + 2 = -1
          // -1 + 1 = 0

                        // !prefixSum - k = -2 - 1 = -3
          // !prefixSum - k = -3 - 1 = -4
           // prefixSum -k = -1 - 1 = -2
          // prefixSum -k = 1-1 = 0
            if (prefixSumMap.containsKey(prefixSum - k)){
                int subarrayLength = i - prefixSumMap.get(prefixSum - k);
                // 2 - prefixSumMap.get(-1 - 1)
              //   2- prefixSumMap.get(-2)
              // 2 - 0 
              // 2 
              // ----
              // 3 - prefixSumMap.get( 0- 1)
              // 3 - 2
              // 1

                maxLen = Math.max(maxLen, subarrayLength);
                // maxLen = 2;
              // maxLen = (2, 1) = 2
            }
                        // ! -2 // !-3
            if (!prefixSumMap.containsKey(prefixSum)){
                prefixSumMap.put(prefixSum, i);
              // -2, 0
              // -3, 1
              // -1, 2
              // 0, 3 
            }

        }

        return maxLen; // 2
    }
}

// TC: O(n)
// SC: O(n)

???? 没懂....