文章目录[隐藏]
Description
给你一个整数数组 nums 和一个整数 k ，请你统计并返回该数组中和为 k 的连续子数组的个数。
CODE
- Time Limit Exceeded
class Solution:
def subarraySum(self, nums, k: int) -> int:
self.preNums = [0]
count = 0
for i in range(len(nums)):
print(i)
self.preNums.append(self.preNums[i] + nums[i])
print(self.preNums)
for i in range(len(self.preNums)):
j = i
while j < len(self.preNums) - 1:
print('i' + str(i) + '\tj' + str(j))
print(self.preNums[j+1] - self.preNums[i])
if (self.preNums[j+1] - self.preNums[i]) == k:
count += 1
j += 1
print("####################")
return count
s = Solution()
nums = [1,-1,1,-1]
print("#####################")
print(s.subarraySum(nums,0))
- Accepted
和为k,数量字典创建位置不通为啥结果不一样？
class SolutionTwo:
def subarraySum(self, nums, k: int) -> int:
self.preNums = [0]
count = 0
for i in range(len(nums)):
self.preNums.append(self.preNums[i] + nums[i])
print(self.preNums)
preDict = {}
for j in self.preNums:
# 为啥不能放到这儿？
# preDict[j] = preDict.get(j,0) + 1
# print(preDict)
print("需要寻找的数" + str(j - k))
# 用dict类是为了避免有重复值情况的发生，避免遗漏统计
# 如果前面有这个前缀和，则直接更新答案
if j - k in preDict:
# count += preDict.get(j - k)
print("preDict的数量：" + str(preDict[j - k]))
count += preDict[j - k]
print(count)
# print(count)
# 为啥只能放到这儿？
preDict[j] = preDict.get(j,0) + 1
print(preDict)
print("####################")
return count
s = SolutionTwo()
nums = [1,-1,1,-1]
print("#####################")
print(s.subarraySum(nums,0))
