leetcode：560. 和为 K 的子数组

题目

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

示例：

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

解答 & 代码

前缀和 + 哈希表
前缀和是从 0 到当前位置所有元素的和。

  1. class Solution {
  2. public:
  3.     int subarraySum(vector<int>& nums, int k) {
  4.         // 哈希表：key = 前缀和，val=该前缀和出现的次数
  5.         unordered_map<int, int> prefixSumCnt;
  6.         prefixSumCnt[0] = 1;    // 初始填入子数组为空的情况，前缀和为 0，出现 1 次
  8.         int result = 0;            // 和为 k 的连续子数组的个数
  9.         int preSum = 0;            // 当前的前缀和
  10.         for(int i = 0; i < nums.size(); ++i)
  11.         {
  12.             preSum += nums[i];    // 用当前的值更新前缀和
  13.             // 如果哈希表中存在前缀和 preSum - k，
  14.             // 则其个数就是以当前位置为末尾的、和为 k 的连续子数组的个数，更新 result
  15.             if(prefixSumCnt.find(preSum - k) != prefixSumCnt.end())
  16.                 result += prefixSumCnt[preSum - k];
  18.             // 将当前的前缀和在哈希表中的出现次数 +1
  19.             if(prefixSumCnt.find(preSum) == prefixSumCnt.end())
  20.                 prefixSumCnt[preSum] = 1;
  21.             else
  22.                 ++prefixSumCnt[preSum];
  23.         }
  24.         return result;
  25.     }
  26. };

复杂度分析：设数组长度为 N

  • 时间复杂度 O(N)
  • 空间复杂度 O(N)：哈希表在最坏情况下可能右 N 个不同的键值

执行结果：

  1. 执行结果：通过
  3. 执行用时：68 ms, 在所有 C++ 提交中击败了 59.15% 的用户
  4. 内存消耗：35.2 MB, 在所有 C++ 提交中击败了 78.70% 的用户