leetcode hot100刷题日记——6.和为 K 的子数组

解答：前缀和思想，见灵茶山艾府大大题解。

（1）前缀和思想：

• 前缀和数组prefix_sum的定义是prefix_sum[i] = nums[0] + nums[1] + … + nums[i]。
• 如果存在两个前缀和prefix_sum[j]和prefix_sum[i]满足prefix_sum[i] - prefix_sum[j] = k，则子数组nums[j+1…i]的和为k。
• 因此，问题转化为寻找满足prefix_sum[i] - k = prefix_sum[j]的索引对(i, j)。

（2）哈希表优化：

• 使用哈希表cnt记录前缀和出现的次数。键为前缀和的值，值为该前缀和出现的次数。
• 初始化时，cnt[0] = 1是为了处理从数组起点开始的子数组（即prefix_sum[i] = k的情况）。

（3）迭代过程：

• 遍历数组，逐步计算前缀和s。
• 对于每个s，检查s - k是否存在于哈希表中。如果存在，说明存在前缀和为s - k的位置，对应子数组的和为k，将对应次数累加到结果ans。
• 将当前前缀和s加入哈希表，供后续迭代使用。

class Solution {
public:int subarraySum(vector<int>& nums, int k) {int n=nums.size();int ans=0;//s[0]=0 单独统计//如果有个前缀和正好等于k，也是需要统计次数的unordered_map<int ,int> cnt{{0,1}};int s=0;//存储前缀和的变量for(int i=0;i<n;i++){s+=nums[i];//不断计算前缀和ans+=cnt.contains(s-k)?cnt[s-k]:0;cnt[s]++;}return ans;}
};

（4）时间与空间复杂度

• 时间复杂度：O(n)
  遍历数组一次，每次操作哈希表的时间为均摊O(1)。
• 空间复杂度：O(n)
  哈希表最多存储n个前缀和。