LeetCode 560. 和为 K 的子数组

2022-09-01  本文已影响0人  草莓桃子酪酪
题目

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

例:
输入:nums = [1,1,1], k = 2
输出:2

方法一:暴力解法
class Solution(object):
    def subarraySum(self, nums, k):
        count = 0
        for i in range(len(nums)):
            sum = 0
            for j in range(i, len(nums)):
                sum += nums[j]
                if sum == k:
                    count += 1
        return count

超出时间限制

方法二:前缀和
class Solution(object):
    def subarraySum(self, nums, k):
        count = 0
        preSums = collections.defaultdict(int)
        preSums[0] = 1
        presum = 0
        for i in range(len(nums)):
            presum += nums[i]
            count += preSums[presum-k]
            preSums[presum] += 1      
        return count
相关知识
参考

代码相关:https://leetcode.cn/problems/subarray-sum-equals-k/solution/python3-by-wu-qiong-sheng-gao-de-qia-non-w6jw/
defaultdict:https://blog.csdn.net/u014248127/article/details/79338543 https://blog.csdn.net/jiaxinhong/article/details/108398099

上一篇 下一篇

猜你喜欢

热点阅读