力扣-560.和为K的子数组

题目描述

560.和为K的子数组

class Solution { public int subarraySum(int[] nums, int k) { int res = 0; // 使用哈希表存储前缀和及其出现次数 HashMap<Integer, Integer> map = new LinkedHashMap<>(); map.put(0, 1); int sum = 0; for (int i = 0; i < nums.length; i++) { sum += nums[i]; if (map.containsKey(sum - k)) { res += map.get(sum - k); } map.put(sum, map.getOrDefault(sum, 0) + 1); } return res; }}

小结：基于前缀和 + 哈希表的查找优化将O(n²)的暴力解法优化为O(n)的高效解法，核心思想是两个前缀和作差即为子数组的和。