🟡 剑指 Offer II 010. 和为 k 的子数组

LeetCode 提示

题目难度 中等

原题链接 🔗 leetcode

题解1

思路是前缀和+哈希表

愚昧的实现：

class Solution {    public int subarraySum(int[] nums, int k) {        int n = nums.length;        Map<Integer, List<Integer>> sumMap = new HashMap<>();        int[] sums = new int[n+1];        int sum = 0;        for (int i=0; i<n; i+=1) {            sum += nums[i];
            sums[i+1] = sum;            if (!sumMap.containsKey(sum)) {                sumMap.put(sum, new ArrayList<>());            }            sumMap.get(sum).add(i);        }
        int cnt = 0;
        for (int i=0; i<n; i+=1) {            int delta = k + sums[i];
            if (!sumMap.containsKey(delta)) {                continue;            }            for (int idx : sumMap.get(delta)) {                if (idx >= i) {                    cnt += 1;                }            }        }
        return cnt;    }}

机智的实现：

class Solution {    public int subarraySum(int[] nums, int k) {        Map<Integer, Integer> pre = new HashMap<>();        int sum = 0, delta, res = 0;        pre.put(0, 1);
        for (int n: nums) {            sum += n;
            delta = sum - k;                        res += pre.getOrDefault(delta, 0);
            pre.put(sum, pre.getOrDefault(sum, 0)+1);        }
        return res;    }}