和为 K 的子数组【哈希】【子串】

发布时间:2024年01月06日

Problem: 560. 和为 K 的子数组

思路 & 解题方法

如果子数组是从start到end
那么用前缀和pre来表示的话,这个子数组的和就是pre[end] - pre[start - 1]
即:
pre[end] - pre[start -  1] == k
可以转换成:
pre[start - 1] == pre[end] - k
所以可以遍历end,pre[end] - k的值可以在O(1)时间复杂度内获得。
那题目就变成了找前面有几个pre[start - 1]。
这个可以用hash来存,所以总的时间复杂度仅为O(n)。

复杂度

时间复杂度:

添加时间复杂度, 示例: O ( n ) O(n) O(n)

空间复杂度:

添加空间复杂度, 示例: O ( n ) O(n) O(n)

Code

class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:
        length = len(nums)
        ans = 0
        pre = [0] * length
        pre[0] = nums[0]
        for i in range(1, length):
            pre[i] = pre[i - 1] + nums[i]

        d = dict()
        d[0] = 1
        for end in range(length):
            if pre[end] - k in d:
                ans += d[pre[end] - k]
            if pre[end] in d:
                d[pre[end]] += 1
            else:
                d[pre[end]] = 1
        return ans
class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:
        length = len(nums)
        ans = 0
        pre = 0
        d = dict()
        d[0] = 1
        for end in range(length):
            pre += nums[end]
            if pre - k in d:
                ans += d[pre - k]
            if pre in d:
                d[pre] += 1
            else:
                d[pre] = 1
        return ans
文章来源:https://blog.csdn.net/qq_45985728/article/details/135431472
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。