560. 和为 K 的子数组

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

Approach 1，前缀和+哈希表

class Solution {
    public int subarraySum(int[] nums, int k) {
        int n = nums.length;
        int[] pre = new int[n+1];
        for (int i = 0; i < n; i++) {
            pre[i+1] = nums[i] + pre[i];
        }

        int cnt = 0;
        for (int i = 1; i < pre.length; i++) {
            int a = pre[i];
            for (int j = i-1; j >= 0; j--) {
                if (a - pre[j] == k) {
                    cnt++;
                }
            }
        }
        return cnt;
    }
}

优化后

class Solution {
    public int subarraySum(int[] nums, int k) {
        int n = nums.length;
        int[] pre = new int[n+1];
        for (int i = 0; i < n; i++) {
            pre[i+1] = nums[i] + pre[i];
        }

        int cnt = 0;
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 1; i < pre.length; i++) {
            int target = pre[i] - k;
            if (pre[i] == k) cnt++;
            cnt += map.getOrDefault(target, 0);
            map.put(pre[i], map.getOrDefault(pre[i], 0)+1);
        }
        return cnt;
    }
}

再优化：

class Solution {
    public int subarraySum(int[] nums, int k) {
        int n = nums.length;
        int[] pre = new int[n + 1];
        for(int i = 1; i <= n; i++) {
            pre[i] = pre[i - 1]  + nums[i - 1];
        }
        int cnt = 0;
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i <= n; i++) {
            int t = pre[i] - k;
            cnt += map.getOrDefault(t, 0);
            map.put(pre[i], map.getOrDefault(pre[i], 0) + 1);
        }
        return cnt;
    }
}