力扣热门100题之和为K的子数组

核心原理

1. 什么是前缀和？

preSum[i]= 数组前 i 个元素的总和

• 从下标j+1到i的子数组和 =preSum[i] - preSum[j]

2. 题目转化

我们要找：

preSum[i] - preSum[j] = k

变形得到核心公式：

preSum[j] = preSum[i] - k

只要前面出现过preSum[i] - k，就找到了一个和为 k 的子数组

完整代码实现：

class Solution { public int subarraySum(int[] nums, int k) { // key：前缀和 value：这个前缀和出现的次数 Map<Integer, Integer> map = new HashMap<>(); // 初始化：前缀和为 0 出现 1 次 map.put(0, 1); int count = 0; // 记录答案个数 int preSum = 0; // 当前前缀和 for (int num : nums) { preSum += num; // 累加，计算当前前缀和 // 核心公式：如果 preSum - k 存在，就说明找到了符合条件的子数组 if (map.containsKey(preSum - k)) { count += map.get(preSum - k); } // 把当前前缀和存入 map map.put(preSum, map.getOrDefault(preSum, 0) + 1); } return count; } }