题解 | JAVA 前缀和#和为K的连续子数组# [P0-T2]

连续子数组和的问题 -> 前缀和

import java.util.*;

public class Solution {
  public int maxlenEqualK (int[] arr, int k) {
    // prefixSumMap: 前缀和 -> 前缀和为sum的最小下标
    Map<Integer, Integer> prefixSumMap = new HashMap<>();
    prefixSumMap.put(0, -1);
    
    int sum_cur = 0;
    int maxLen = 0;
    for (int i = 0; i < arr.length; i++) {
      sum_cur += arr[i];

      // sum_cur - sum_prev = k
      int sum_prev = sum_cur - k;
      if (prefixSumMap.containsKey(sum_prev))
        maxLen = Math.max(i - prefixSumMap.get(sum_prev), maxLen);
      
      // maintain最小下标
      prefixSumMap.put(sum_cur, 
          Math.min(prefixSumMap.getOrDefault(sum_cur, Integer.MAX_VALUE), i));
    }

    return maxLen;
  }
}