给你一个整数数组 nums 和一个整数 k ，请你统计并返回该数组中和为 k 的连续子数组的个数。

• https://leetcode-cn.com/problems/subarray-sum-equals-k/

• 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))

要不赞赏一下?

微信

支付宝

PayPal

Bitcoin