leetcode 560 和为k的子数组

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

示例：

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

---

解题思路与代码思路：

理解前缀和的思路

对于数组nums，我们可以创建一个前缀和数组preSum：

$preSum[i]=nums[0...(i-1)]$ 的和

由此可推出 ：

$nums[i...j]的和=preSum[j+1]-preSum[i]$

可以帮助我们去除重复计算。 比如 前5项的和 - 前3项的和 = 第4项~第5项的和。 (1+2+3+4+5) - (1+2+3) = 4+5

暴力法

每一轮循环的所有数的总和用一个变量prefixSum记录下来。

前缀哈希法

在第二层循环中，我们要计算的是本轮有多少个 j 加起来等于k，每次找到和可以为k，就count加一；根据前缀和的规则，我们只需要知道prefixSum减去k值，即当前位置前缀和减去之前某一位的前缀和等于目标值

---

代码：

暴力法

class Solution: def subarraySum(self, nums, k): count = 0 for i in range(len(nums)): prefixSum = 0 for j in range(i,len(nums)): prefixSum += nums[j] if prefixSum == k: count +=1 return count

前缀哈希法

class Solution: def subarraySum(self, nums, k): prefixSumDict = {0:1} count = 0 prefixSum = 0 for ele in nums: prefixSum += ele sub = prefixSum - k if sub in prefixSumDict: # 差值的计数 count += prefixSumDict[sub] prefixSumDict[prefixSum] = prefixSumDict.get(prefixSum, 0) + 1 #已经存在的数的计数 return count

---

$复杂度分析：$

暴力法 时间复杂度：O(N^2)空间复杂度：O(1) 前缀哈希法 时间复杂度：O(N)空间复杂度：O(N)

利用前缀和快速查找某个分数段的人数

scores = [10,22,60,80,82,90,80] # scores = list(scores) print(scores) count = [0]*100 for i in scores: count[i] +=1 print(count) for i in range(1,len(count)): count[i] = count[i] + count[i-1] print(count) count[90] - count[80] 生成成绩scores建立一个数组，利用index对应分数来记录各个分数的人数然后构造了前缀和现在我们就可以查找分数段人数。例如90分到80分的人数，结果是2，这里的结果没有包含80，所以如果希望包含80，要改成$count[90]-count[79]$