题目-和为 K 的子数组

解法1：两层for循环

public class T560 {
    public static int subarraySum(int[] nums, int k) {
        int res = 0;
        for (int i = 0; i < nums.length; i++) {
            int tempSum = 0;
            for (int j = i; j < nums.length; j++) {
                tempSum += nums[j];
                if (tempSum == k) {
                    res++;
                }
            }
        }
        return res;
    }

    public static void main(String[] args) {
        int[] nums = {1, -1, 0};
        int k = 0;
        System.out.println(subarraySum(nums, k));
    }
}

解法2：前缀和+哈希

• 前缀和：前缀和数组 sum[i] 表示从数组起点到位置 i 的元素之和。
• 哈希表：使用哈希表记录前缀和出现的次数，这样在遍历数组时可以快速找到符合条件的子数组。

public class T560 {
    public static int subarraySum(int[] nums, int k) {
        int res = 0;
        Map<Integer, Integer> map = new HashMap<>();
        map.put(0, 1);
        // 
        int currentSum = 0;
        for (int i = 0; i < nums.length; i++) {
            //sum[i...j]=sum[j]-sum[i-1]
            currentSum += nums[i];
            if (map.containsKey(currentSum - k)) {
                res += map.get(currentSum - k);
            }
            map.put(currentSum, map.getOrDefault(currentSum, 0) + 1);
        }
        return res;
    }

    public static void main(String[] args) {
        int[] nums = {1, -1, 0};
        int k = 0;
        System.out.println(subarraySum(nums, k));
    }
}

详细解释 currentSum - k
设 currentSum 表示当前的前缀和，也就是从数组起点到当前位置的元素之和。我们希望找到一个子数组，使得这个子数组的和等于 k。假设我们当前遍历到数组位置 j，当前的前缀和为 currentSum。

如果存在某个位置 i 使得从 i 到 j 的子数组和等于 k，根据前缀和的定义，有：sum[j]-sum[i-1]=k 其中sum[j]就是currentSum

变形一下：sum[j]-sum[i-1]=k ➡️sum[j]-k=sum[i-1]➡️currentSum-k=sum[i-1]。（因为已知k，不知道sum[i-1] ，所以把k移到等号左边，看map中是否包含sum[i-1]，包含则说明i到j的和为k）

为什么是res += map.get(currentSum - k);而不是res += 1;因为可能存在多个前缀和为currentSum - k。搞懂map存的什么