README.md

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

题目描述

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

 

示例 1 :

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

示例 2 :

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

 

提示:

• 1 <= nums.length <= 2 * 104
• 1000 <= nums[i] <= 1000

• -107 <= k <= 107

 

注意：本题与主站 560 题相同： https://leetcode.cn/problems/subarray-sum-equals-k/

解法

数组中既有正数又有负数，无法使用双指针。可以利用前缀和思想，快速判断子数组的和

Python3

class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:
        d = defaultdict(int, {0: 1})
        ans, sum = 0, 0
        for num in nums:
            sum += num
            ans += d[sum - k]
            d[sum] += 1
        return ans

Java

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

Go

func subarraySum(nums []int, k int) int {
	m := map[int]int{0: 1}
	sum, ans := 0, 0
	for _, num := range nums {
		sum += num
		ans += m[sum-k]
		m[sum]++
	}
	return ans
}

C++

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        if (nums.size() < 0) return 0;

        int presum = 0;
        int count = 0;
        unordered_map<int, int> mp;
        mp[0] = 1;

        for (int right = 0; right < nums.size(); right++) {
            presum += nums[right];
            count += mp[presum - k];
            mp[presum]++;
        }

        return count;
    }
};

...