C/C++---------------LeetCode第560. 和为 K 的子数组

题目及要求

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

子数组是数组中元素的连续非空序列。

示例 1：

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

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

提示：

1 <= nums.length <= 2 * 104
-1000 <= nums[i] <= 1000
-107 <= k <= 107

暴力算法

思路：枚举所有结果进行对比
时间复杂度为O(n^2)
空间复杂度为O(1)

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
   int count=0,n=nums.size();
   for(int start=0;start<n;++start){
       int sum=0;
       for(int end=start;end>=0;--end){
           sum+=nums[end];
           if(sum==k){
               count++;
           }
       }
   }
   return count;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

前缀和+哈希

前缀和：前缀和是指从数组开头到当前位置的元素之和
思路：我们遍历数组时，计算每个位置的前缀和，并将前缀和存储在哈希表中，当我们计算到第 i 个位置时，就可以检查哈希表中是否存在前面某个位置的前缀和等于 (当前前缀和 - k)，如果存在这样的前缀和，那么说明存在一个子数组的和为 k

unordered_map<int, int> prefixSumCount; // 前缀和以及出现的次数
    int count = 0;
    int prefixSum = 0;

    prefixSumCount[0] = 1; // 初始化前缀和为0的情况出现了一次

    for (int num : nums) {
        prefixSum += num; // 计算当前位置的前缀和
        if (prefixSumCount.count(prefixSum - k)) { // 如果存在前缀和为 prefixSum - k 的情况，说明存在子数组的和为 k
            count += prefixSumCount[prefixSum - k]; // 更新计数
        }
        prefixSumCount[prefixSum]++; // 更新当前前缀和出现的次数
    }

    return count;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15