Keshawn_lu's Blog

Leetcode 560. 和为K的子数组

字数统计: 445阅读时长: 1 min
2020/05/15 Share

题目简介:

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

示例 1 :

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

说明 :

  1. 数组的长度为 [1, 20,000]。
  2. 数组中元素的范围是 [-1000, 1000] ,且整数 k 的范围是 [-1e7, 1e7]。

思路:

首先最先想到的是暴力法,两次循环记录每个子数组的和,若子数组元素和与 k 相等则count++,结果很意料之中的超时了。

所以就开始想其他的方法,我们可以定义一个sumsum[i]代表的为数组下标从0 ~ i数据的和,若子数组[i....j]的和为 k ,那么sum[j] - sum[i] = k,所以我们定义一个哈希表,在循环过程中,若我们当前的sum - k在哈希表中存在,即之前有元素和达到了sum - k,即这一段子数组的和便为 kcount += Hash[sum - k]即可,最后再把当前元素和放至哈希表中。

代码如下:

  • 暴力法(超时)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
int subarraySum(vector<int>& nums, int k) {

int count = 0;

for(int i = 0; i < nums.size(); i++){

int res = 0;
for(int j = i; j < nums.size(); j++){

res += nums[j];
if(res == k){

count++;
}
}
}

return count;

}
};
  • Hash表法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
int subarraySum(vector<int>& nums, int k) {

unordered_map<int,int> Hash{{0, 1}}; //无元素时总和为0,次数为1
int sum = 0; //存储之前的数的总和
int count = 0;

for(int i = 0; i < nums.size(); i++){

sum += nums[i];

if(Hash.find(sum - k) != Hash.end()){

count += Hash[sum - k]; //说明找到了该子数组
}

Hash[sum]++;

}

return count;

}
};
CATALOG
  1. 1. 题目简介:
  2. 2. 思路:
  3. 3. 代码如下: