LeetCode 560. 和为K的子数组

发表于 更新于 分类于 Changyan： 本文字数： 452 阅读时长 ≈ 2 分钟

题目描述

和为K的子数组

给定一个整数数组和一个整数 k，你需要找到该数组中和为 k 的连续的子数组的个数。

示例 1 :

输入: nums = [1,1,1], k = 2
输出: 2 , [1,1] 与 [1,1] 为两种不同的情况。

解法一（滑动窗口）

思路是采用滑动窗口的方式，将窗口的大小（即sub_size，子数组大小）从1一直增长到数组大小，测试所有窗口大小下的情况，时间复杂度为 O(n2)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
  int subarraySum(vector<int>& nums, int k) {
    int size = nums.size(), count = 0;
    for (int sub_size = 1; sub_size <= size; sub_size++) {
      int windows_sum = 0;
      for (int i = 0; i < sub_size; i++) {
        windows_sum += nums[i];
      }
      if (windows_sum == k)
        count++;
      for (int j = sub_size; j < size; j++) {
        windows_sum += nums[j] - nums[j - sub_size];
        if (windows_sum == k)
          count++;
      }
    }
    return count;
  }
};

解法二（哈希表）

解法二是LeetCode官方给出的解法——采用哈希表，算法的时间复杂度为O(n)。

思想是：如果 sum[j] - sum[i] = k，则索引i和j之间的元素和为k；而 sum[j] - k = sum[i]也是一样的意思。

我们用哈希表去依次记录从0一直到size - 1的累加和，以及累加和出现的次数。每次算得一个位置的累加和sum，就判断 sum - k 的结果是否在hash表中，以及出现的次数，这就表示现在求得的累加和与之前某个位置的累加和之间的元素和为K，用count记录得到最终结果。

注意哈希表一开始要 map.insert({0, 1});，这步不能忘了。

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