Medium

题目描述

给你一个整数数组 nums 和一个整数 k ，请你统计并返回该数组中和为 k 的连续子数组的个数。

示例 1：

输入：nums = [1,1,1], k = 2
输出：2

示例 2：

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

提示：

  • 1 <= nums.length <= 2 * 10^4
  • -1000 <= nums[i] <= 1000
  • -10^7 <= k <= 10^7

解题思路

解题思路

方法一：暴力解法 枚举所有可能的子数组，计算每个子数组的和，统计和为 k 的子数组个数。时间复杂度为 O(n²)。

方法二：前缀和 + 哈希表（推荐） 这是最优解法，核心思想是利用前缀和的性质。

对于任意两个位置 i 和 j（i < j），如果从位置 i+1 到位置 j 的子数组和为 k，那么有： prefixSum[j] - prefixSum[i] = k，即 prefixSum[i] = prefixSum[j] - k

算法步骤：

  1. 使用哈希表存储前缀和出现的次数
  2. 遍历数组，计算当前位置的前缀和
  3. 查找哈希表中是否存在 prefixSum - k，如果存在，说明找到了和为 k 的子数组
  4. 将当前前缀和加入哈希表

关键点是初始化哈希表时要加入 {0: 1}，表示前缀和为 0 出现了 1 次，这样可以处理从数组开头开始的子数组。

时间复杂度 O(n)，空间复杂度 O(n)，是最优解法。

代码实现

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        unordered_map<int, int> prefixSumCount;
        prefixSumCount[0] = 1;
        
        int prefixSum = 0;
        int count = 0;
        
        for (int num : nums) {
            prefixSum += num;
            
            if (prefixSumCount.find(prefixSum - k) != prefixSumCount.end()) {
                count += prefixSumCount[prefixSum - k];
            }
            
            prefixSumCount[prefixSum]++;
        }
        
        return count;
    }
};

class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:
        prefix_sum_count = {0: 1}
        prefix_sum = 0
        count = 0
        
        for num in nums:
            prefix_sum += num
            
            if prefix_sum - k in prefix_sum_count:
                count += prefix_sum_count[prefix_sum - k]
            
            prefix_sum_count[prefix_sum] = prefix_sum_count.get(prefix_sum, 0) + 1
        
        return count

public class Solution {
    public int SubarraySum(int[] nums, int k) {
        Dictionary<int, int> prefixSumCount = new Dictionary<int, int>();
        prefixSumCount[0] = 1;
        
        int prefixSum = 0;
        int count = 0;
        
        foreach (int num in nums) {
            prefixSum += num;
            
            if (prefixSumCount.ContainsKey(prefixSum - k)) {
                count += prefixSumCount[prefixSum - k];
            }
            
            if (prefixSumCount.ContainsKey(prefixSum)) {
                prefixSumCount[prefixSum]++;
            } else {
                prefixSumCount[prefixSum] = 1;
            }
        }
        
        return count;
    }
}

var subarraySum = function(nums, k) {
    const prefixSumCount = new Map();
    prefixSumCount.set(0, 1);
    
    let prefixSum = 0;
    let count = 0;
    
    for (const num of nums) {
        prefixSum += num;
        
        if (prefixSumCount.has(prefixSum - k)) {
            count += prefixSumCount.get(prefixSum - k);
        }
        
        prefixSumCount.set(prefixSum, (prefixSumCount.get(prefixSum) || 0) + 1);
    }
    
    return count;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

解法时间复杂度空间复杂度
前缀和 + 哈希表O(n)O(n)
暴力解法O(n²)O(1)

相关题目