leetcode560-- Subarray Sum Equals K

leetcode560-- Subarray Sum Equals K

题目

Given an array of integers and an integer k, you need to find the total number of continuous subarrays whose sum equals to k.

Example 1:

Input:nums = [1,1,1], k = 2
Output: 2

这个题目是找到所有的,不一定是从头开始的,有正有负,也有重复的,中间加起来的还有可能为0, 比如如果列表全是0的话,k也是0的话,就非常多。

思路

刚看到这个题的时候,暴力当然肯定是可以的,但是会超时,

实际上,因为任意的一个连续的子段,都是每两个前n项和的差, 假如我们已经得到了前n项和的数组了,接下来就是要找到这个数组中哪两个的差是k,而且是后者-前者。即

suma + (-sumb) = k,

写到这的时候我想到了two sum的那道题,即采用建立字典的想法.

移一下的话即suma-k=sumb, 其中suma是连续数组比较长的那个.

所以思路就有了

class Solution(object):
    def subarraySum(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: int
        """
        dic = {}
        dic[0] = 1
        summ, result = 0, 0
        for num in nums:
            summ += num
            # 一定要先找,再更新字典
            if summ-k in dic:
                result += dic[summ-k]   ## 说明之前有个和为summ-k 而现在和是summ,且summ是长的序列对应的和,从而是对的
   
            if summ in dic:
                dic[summ] += 1  # 记录和为summ的出现的次数
            else:
                dic[summ] = 1   # 
                
        return result

    

详解如下

   
        dic = {}
        dic[0] = 1
        summ, ret = 0,0
        
        for x in nums:
            
            summ += x
            
            # 先查找
            if summ-k in dic:
                ret += dic[summ-k]  # 从这里可以看出来初始化dic[0]=1很有必要.
          
                                    # 不然如果第一个元素就是k的话,不好处理
            # 再更新字典
            
            if summ in dic:
                dic[summ] += 1
            else:
                dic[summ] = 1
                
                
        return ret
        

打赏,谢谢~~

取消

感谢您的支持,我会继续努力的!

扫码支持
扫码打赏,多谢支持~

打开微信扫一扫,即可进行扫码打赏哦