当前位置 博文首页 > coordinate的博客：Leetcode 560：和为K的数组（最详细的解法！
给定一个整数数组和一个整数 **k，**你需要找到该数组中和为 k 的连续的子数组的个数。
示例 1 :
输入:nums = [1,1,1], k = 2
输出: 2 , [1,1] 与 [1,1] 为两种不同的情况。
说明 :
解题思路
首先想到的解法就是暴力解法，使用三重循环。
class Solution:
def subarraySum(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: int
"""
nums_len, result = len(nums), 0
for i in range(nums_len):
for j in range(i, nums_len):
cur_sum = 0
for l in range(i, j + 1):
cur_sum += nums[l]
if cur_sum == k:
result += 1
return result
上面这种做法显然没有什么参考价值。所以我们思考有没有O(n^2)的解法。同样非常容易想到，我们每次计算[i,len(nums)]这个区间内以i开始的每个小区间的和，记录所以和为k的区间个数。通过遍历nums每个元素i，我们就可以求解出每个以i开始并且和为k的区间个数，最后加在一起即可。
class Solution:
def subarraySum(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: int
"""
nums_len, result = len(nums), 0
for i in range(nums_len):
cur_sum = 0
for j in range(i, nums_len):
cur_sum += nums[j]
if cur_sum == k:
result += 1
return result
有没有更快的办法。有，这个问题可以通过Prefix sum来求解。假设我们令P[i] = A[0] + A[1] + ... + A[i-1]和P[j] = A[0] + A[1] + ... + A[j-1]，那么P[j] - P[i] = A[i] + A[i+1] + ... + A[j-1]。如果P[j] - P[i] == S的话，那么[i,j]就是我们需要的区间。所以我们对于每个j，我们只要计算有多少个i使得P[j] - P[i] == S，这样我们就得到了以P[j]作为右区间并且和为S的区间数。对于A中的每个元素都做同样的处理，最有将所有的结果相加即可。
具体实现上，我们通过hash_map记录P[j]。初始化的时候要注意一个细节，对于dict[0]=1。为什么？因为当P[j]==S时，P[i]=0并且此时我们的result=1。
class Solution:
def subarraySum(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: int
"""
result, cur_sum = 0, 0
sum_dict = {0:1}
for num in nums:
cur_sum += num
if cur_sum - k in sum_dict:
result += sum_dict[cur_sum - k]
sum_dict[cur_sum] = sum_dict.get(cur_sum, 0) + 1
return result
我将该问题的其他语言版本添加到了我的GitHub Leetcode
如有问题，希望大家指出！！！
cs