题解 | #和为K的连续子数组#

import java.util.*;


public class Solution {
    /**
     * max length of the subarray sum = k
     * @param arr int整型一维数组 the array
     * @param k int整型 target
     * @return int整型
     */
    /*
    public int maxlenEqualK (int[] arr, int k) {
        // write code here
        // 暴力破解
        int res = 0; // 定义一个整型变量，用于存放最终的返回结果
        int tmp = 0; // 定义一个整型变量，用于临时存放数据
        for (int i = 0; i < arr.length - 1; i++) {
            tmp = arr[i]; // 获取当前位置上的值
            for (int j = i + 1; j < arr.length; j++) {
                tmp += arr[j];
                if (tmp == k) {
                    res = Math.max(res, j - i + 1);
                }
            }
        }
        return res;
    }
    */
    
    // 使用前缀和 + 哈希的方法，解决这个问题
    public int maxlenEqualK (int[] arr, int k) {
        // 定义一个整型数组，用于存放前缀和
        int[] pre = new int[arr.length];
        // 别忘了，初始化 pre 数组
        pre[0] = arr[0];
        for (int i = 1; i < pre.length; i++) {
            pre[i] = pre[i - 1] + arr[i];
        }
        
        // 定义一个 HashMap，用于存放某个前缀和以及它所在的位置
        HashMap<Integer, Integer> hashMap = new HashMap<>();
        hashMap.put(0, -1);
        // 定义一个整型变量，用于存放最终的返回结果
        int res = 0;
        
        // 说明：区间 [i, j] 的和等于 pre[j] - pre[i - 1]
        for (int i = 0; i < pre.length; i++) {
            
            int tmp = hashMap.getOrDefault(pre[i], -2);
            if (tmp == -2) {
                hashMap.put(pre[i], i);
            }
            
            int index = hashMap.getOrDefault(pre[i] - k, -2);
            if (index != -2) {
                res = Math.max(res, i - index);
            }
        }
        return res;
    }
}