力扣-和为K的子数组

题目-和为 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存的什么