【打卡】子数组和为K

描述
给定一个整数数组和一个整数k，你需要找到连续子数列的和为k的总个数。

样例
样例1

输入: nums = [1,1,1] 和 k = 2
输出: 2
解释:
子数组 [0,1] 和 [1,2]

样例2

输入: nums = [2,1,-1,1,2] 和 k = 3
输出: 4
解释:
子数组 [0,1], [1,4], [0,3] and [3,4]
这里[1,4]是指[1,2,3,4],[0,3]是[0,1,2,3]

法一：暴力求解（因超出时长限制而不被采用）

class Solution:
    """
    @param nums: a list of integer
    @param k: an integer
    @return: return an integer, denote the number of continuous subarrays whose sum equals to k
    """
    def subarraySumEqualsK(self, nums, k):
        # write your code here
        l = len(nums)
        count = 0
        s = 0
        for i in range(l):
            for j in range(i,l):
                s += nums[j]
                if s == k:
                    count += 1
            s = 0
                
        return count

法二：
先求出nums的前i项和；
再创建一个字典用于存储，各个前缀出现的次数，标记nums[i]-k的次数，即和为k的连续子序列的个数。

class Solution:
    """
    @param nums: a list of integer
    @param k: an integer
    @return: return an integer, denote the number of continuous subarrays whose sum equals to k
    """
    # 如果nums[i] - k前面出现过，说明从那个数往后直到i就是一个连续和为k的子序列
    # 故nums[i] - k出现过几次，就加上几次
    def subarraySumEqualsK(self, nums, k):
        # write your code here
        l = len(nums)
        for i in range(1,l):
            nums[i] += nums[i-1]

        d = {0:1}
        ans = 0
        for i in range(l):
            if d.get(nums[i] - k) != None:       # 即nums[i] - k出现的次数
                ans += d[nums[i] - k]
            if d.get(nums[i]) == None:
                d[nums[i]] = 1       # 若nums[i]前面没有出现过，则次数设为1
            else:
                d[nums[i]] += 1      # 如果nums[i]前面已经出现过，则次数+1
        
        return ans

Tips:
dict[‘key’] 只能获取存在的值，若不存在则触发KeyError；
dict.get(key,default = None) 若不存在则返回一个默认值，如果设置了则是设置的，否则就是None

最后

以上就是迅速书本为你收集整理的【打卡】子数组和为K的全部内容，希望文章能够帮你解决【打卡】子数组和为K所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。