Open
Description
Given an array of integers and an integer k, you need to find the total number of continuous subarrays whose sum equals to k.
Example 1:
Input:nums = [1,1,1], k = 2
Output: 2
Constraints:
* The length of the array is in range [1, 20,000].
* The range of numbers in the array is [-1000, 1000] and the range of the integer k is [-1e7, 1e7].
这题求的是子数组内元素之和为指定k值的个数。
首先想到的是遍历所有可能的子数组，最简便的方法是暴力遍历：
class Solution {
public int subarraySum(int[] nums, int k) {
int res = 0, sum = 0, n = nums.length;
for (int i = 0; i < n; ++i) {
sum = 0;
for (int j = i; j < n; ++j) {
sum += nums[j];
if (sum == k) ++res;
}
}
return res;
}
}
接下来，既然题目与累加和有关，我们可以联想到设计一个累加数组sums，sums[i] - sums[[j]的值就是i到j的子数组的累加和。
class Solution {
public int subarraySum(int[] nums, int k) {
int res = 0, sum = 0, n = nums.length;
int[] sums = nums.clone();
if (sums[0] == k) ++res;
for (int i = 1; i < n; ++i) {
sums[i] = nums[i] + sums[i - 1];
if (sums[i] == k) ++res;
for (int j = 0; j < i; ++j) {
if (sums[i] - sums[j] == k)
++res;
}
}
return res;
}
}
然而这种解法跟暴力遍历没什么很大的区别，只不过是用线性空间存储了累加值而已，时间复杂度没有被优化。
为了继续减少时间复杂度，从“存储+累加和”的角度，我们可以联想到利用哈希表代替数组来存储累加和值，那么如何避免陷入上述数组的两层循环思路呢？我们可以利用题目已给的k值，判断是否存在sums[i] - k(显然数组是无法在O(1)的时间内进行判断的)，如果是，value值存储的是出现的次数，加入进结果变量res中。
注意一开始我们要存入(0, 1)，因为sums[i]本身也有可能等于k值。
class Solution {
public int subarraySum(int[] nums, int k) {
int res = 0, sum = 0, n = nums.length;
HashMap<Integer, Integer> map = new HashMap<>();
map.put(0, 1);
for (int i = 0; i < n; ++i) {
sum += nums[i];
if (map.containsKey(sum - k)) {
res += map.get(sum - k);
}
map.put(sum, map.getOrDefault(sum, 0) + 1);
}
return res;
}
}
类似题目：
参考资料：
Metadata
Assignees
Labels
No labels