📃 题目描述

题目链接：

• 剑指 Offer II 010. 和为 k 的子数组 - 力扣（LeetCode） (leetcode-cn.com) (opens new window)
• 560. 和为 K 的子数组 - 力扣（LeetCode） (leetcode-cn.com) (opens new window)

给定一个整数数组和一个整数 k ，请找到该数组中和为 k 的连续子数组的个数。

示例 1 :

输入:nums = [1,1,1], k = 2
输出: 2
解释: 此题 [1,1] 与 [1,1] 为两种不同的情况

示例 2 :

输入:nums = [1,2,3], k = 3
输出: 2

🔔 解题思路

经典前缀和问题：从第一个数到当前数的和，被称为前缀和

暴力

class Solution {
    public int subarraySum(int[] nums, int k) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        
        // 数组中和为 k 的连续子数组的个数
        int res = 0;
        for (int i = 0; i < nums.length; i ++) {
            int sum = 0;
            for (int j = i; j < nums.length; j ++) {
                sum += nums[j];
                if (sum == k) {
                    res ++;
                    // break; 这里不能 break 掉，因为后面可能还有 num = 0，比如 [1,-1,0]
                }
            }
        }

        return res;
    }
}

时间复杂度：O(N^2)

哈希表

可能有同学会想到用双指针做这道题，But 使用双指针解决子数组之和的题目有一个前提条件——数组中的所有数字都是正数。如果数组中的数字有正数、负数和零，那么双指针的思路并不适用，这是因为当数组中有负数时在子数组中添加数字不一定能增加子数组之和，从子数组中删除数字也不一定能减少子数组之和

看下面这张图就能明白：

标红的那段 [j + 1, i]，就是题目要求的和为 k 的子数组

二刷的时候写了一个相对比较容易理解的版本：

class Solution {
    public int subarraySum(int[] nums, int k) {
        // key: 从第一个数到当前数的和，value：这个和出现的次数
        Map<Integer, Integer> map = new HashMap<>();

        // preSum 表示从第一个数到当前数的和（前缀和）
        int preSum = 0;
        // res 表示数组中和为 k 的连续子数组的个数
        int res = 0;

        for (int num : nums) {
            preSum += num;

            // preSum = k
            if (preSum == k) {
                res += 1;
            }

            // 这里不能用 else!
            // 考虑这种情况：k = 0, 且前面也存在前缀和为 0 的子数组
            // 比如 (1, -1, 0), preSum = (1, 0, 0) 
            if (map.containsKey(preSum - k)) {
                res += map.get(preSum - k);
            }

            // 更新 map
            map.put(preSum, map.getOrDefault(preSum, 0) + 1);
        }

        return res;
    }
}

nums[i] == k 这种情况不需要特殊考虑，因为如果 nums[i] == k，比如 1 2 3，k = 3，遍历到 3 的时候，preSum = 1 + 2 + 3 = 6，此时 map 中一定是拥有 preSum - k = 5 的！

这是一刷的代码，事先 map.put(0,1) 可能不太好理解

class Solution {
    public int subarraySum(int[] nums, int k) {
        // key: 从第一个数到当前数的和，value：这个和出现的次数
        Map<Integer, Integer> map = new HashMap<>();
        // 当 preSum = k 的时候，preSum - k = 0，所以我们需要事先填入一个（0，1）的记录，防止处理不到这种情况
        map.put(0, 1);

        // preSum 表示从第一个数到当前数的和（前缀和）
        int preSum = 0;
        // res 表示数组中和为 k 的连续子数组的个数
        int res = 0;

        for (int num : nums) {
            preSum += num;
            res += map.getOrDefault(preSum - k, 0);
            // 更新 map
            map.put(preSum, map.getOrDefault(preSum, 0) + 1);
        }
        

        return res;
    }
}

时间复杂度：O(N)