代码语言：javascript复制
今天分享leetcode第18篇文章，也是leetcode第560题—和为K的子数组（Subarray Sum Equals K），地址是：https://leetcode.com/problems/subarray-sum-equals-k/【英文题目】（学习英语的同时，更能理解题意哟~）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
Note: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，你需要找到该数组中和为 k 的连续的子数组的个数。示例 1 :输入:nums = [1,1,1], k = 2
输出: 2 , [1,1] 与 [1,1] 为两种不同的情况。
说明 :数组的长度为 [1, 20,000]。数组中元素的范围是 [-1000, 1000] ，且整数 k 的范围是 [-1e7, 1e7]。【思路】本题和「连续的子数组和」类似，同样可以有两种解法。一是暴力破解，使用数组sums，数组元素sums[i]存储nums数组0->i子数组和，然后循环嵌套遍历存在多少个sums[j] - sums[i]等于k。但是遗憾的是，时间复杂度较高，不能通过测试。二是使用字典（hash），使用字典sums，key为子数组和，value为key出现次数。遍历数组，遇到一个0->i的子数组和tmp_sum，判断其是否在sums中，如果在则增加count相应次数，同时需要增加sums数组中tmp_sum的次数。时间复杂度为O(n)。注意：字典需要默认0出现一次，否则tmp_sum == k时，不能增加count次数。【代码】python版本class Solution(object):
def subarraySum(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: int
"""
length = len(nums)
# 字典存储某个num出现次数，默认0出现1次
sums = {0:1}
tmp_sum = 0
count = 0
# 统计0->i的元素之和
for i in range(length):
tmp_sum = nums[i]
# tmp_sum == k 或者 tmp_sum - 某个sums[j] == k
# 都是求 tmp_sum - k 出现次数
count = sums.get(tmp_sum - k, 0)
sums[tmp_sum] = sums.get(tmp_sum, 0) 1
return count
C 版本class Solution {
public:
int subarraySum(vector<int>& nums, int k) {
map<int, int> sums;
sums[0] = 1;
int tmp_sum = 0;
int count = 0;
for(int i=0; i < nums.size(); i ){
tmp_sum = nums[i];
// tmp_sum == k 或者 tmp_sum - 某个sums[j] == k
// 都是求 sums[i] - k 出现次数
if(sums.find(tmp_sum - k) != sums.end())
count = sums[tmp_sum - k];
// tmp_sum出现次数 1
if(sums.find(tmp_sum) == sums.end())
sums[tmp_sum] = 1;
else
sums[tmp_sum] = 1;
}
return count;
}
};
