小型企业网站排名前十网站开发及技术路线

R2-前缀和专题

目录

前缀和+哈希表

双指针

ps:

第一眼过去，这题应该能用双指针解出来，应该也能用前缀和解题。

前缀和+哈希表

适用于 nums[i] 值不固定为 0 和 1 的其他情况

class Solution:def numSubarraysWithSum(self, nums: List[int], goal: int) -> int:n=len(nums)prenum=[0]+list(accumulate(nums))dict=defaultdict(int,{0:1})ret=0for i in range(n):r=prenum[i+1]l=r-goalret+=dict[l]dict[r]+=1return ret

 

双指针

 

class Solution:def numSubarraysWithSum(self, nums: List[int], goal: int) -> int:#就是说[l1,l2]---r,左集合的个数代表当前i下所有可能，i移动就行n=len(nums)ret=l1=l2=s1=s2=0for i in range(n):s1+=nums[i]s2+=nums[i]#左集合左右端点的移动while l1<=i and s1>goal:s1-=nums[l1]l1+=1while l2<=i and s2>=goal:s2-=nums[l2]l2+=1ret+=l2-l1return ret

ps:

1.python功能使用

2.第一种方法中哈希表定义和使用也很ok啊