《剑指 Offer》专项突破版 - 面试题 10 : 和为 k 的子数组（C++ 实现）- 前缀和 + 哈希表

目录

前言

一、暴力求解

二、前缀和 + 哈希表

前言

题目链接：LCR 010. 和为 K 的子数组 - 力扣（LeetCode）

题目：

输入一个整数数组和一个整数 k，请问数组中有多少个数字之和等于 k 的连续子数组？例如，输入数组 [1, 1, 1]，k 的值等于 2，有 2 个连续子数组之和等于 2。

?

一、暴力求解

class Solution {
public:
 ? ?int subarraySum(vector<int>& nums, int k) {
 ? ? ? ?int n = nums.size();
 ? ? ? ?int count = 0;
 ? ? ? ?for (int i = 0; i < n; ++i)
 ? ? ?  { ?
 ? ? ? ? ? ?int sum = 0;
 ? ? ? ? ? ?for (int j = i; j < n; ++j)
 ? ? ? ? ?  {
 ? ? ? ? ? ? ? ?sum += nums[j];
 ? ? ? ? ? ? ? ?if (sum == k)
 ? ? ? ? ? ? ? ? ? ?++count;
 ? ? ? ? ?  }
 ? ? ?  }
 ? ? ? ?return count;
 ?  }
};

这种解法的时间复杂度是 O(n^2)。

二、前缀和 + 哈希表

从头到尾扫描数组中的数字时求出前 i 个数字之和，并且将和保存下来。数组的前 i 个数字之和记为 x，如果存在一个 j（j < i），数组的前 j 个数字之和为 x - k，那么从数组中第 j + 1 个数字开始到第 i 个数字结束的子数组之和为 k。

这个题目需要计算和为 k 的子数组的个数。当扫描到数组的第 i 个数字并求得前 i 个数字之和是 x 时，需要知道在 i 之前存在多少个 j 并且前 j 个数字之和等于 x - k。所以，对于每个 i，不但要保存前 i 个数字之和，还要保存每个和出现的次数。分析到这里就会知道我们需要一个哈希表，哈希表的建是前 i 个数字之和，值为每个和出现的次数。

class Solution {
public:
 ? ?int subarraySum(vector<int>& nums, int k) {
 ? ? ? ?int n = nums.size();
 ? ? ? ?int count = 0;
 ? ? ? ?unordered_map<int, int> sumToCount;
 ? ? ? ?sumToCount[0] = 1;
 ? ? ? ?int sum = 0;
 ? ? ? ?for (int i = 0; i < n; ++i)
 ? ? ?  {
 ? ? ? ? ? ?sum += nums[i];
 ? ? ? ? ? ?if (sumToCount.count(sum - k))
 ? ? ? ? ? ? ? ?count += sumToCount[sum - k];
 ? ? ? ? ? ?
 ? ? ? ? ? ?++sumToCount[sum];
 ? ? ?  }
 ? ? ? ?return count;
 ?  }
};

该解法的时间复杂度是 O(n)，空间复杂度也是 O(n)。