【leetcode】560. Subarray Sum Equals K

时间:2023-02-09 16:18:26

题目如下:【leetcode】560. Subarray Sum Equals K解题思路:本题的关键在于题目限定了是连续的数组,我们用一个dp数组保存第i位到数组末位的和。例如nums = [1,1,1],那么dp = [3,2,1], dp[i]表示nums[i]+nums[i+1] +...+nums[len(nums)-1],有了这一个dp数组后,我们很容易就可以得到递推表达式 sum(i,j) = dp[i] - dp[j+1]。最后,顺序遍历dp数组,对于任意的dp[i],只要找到对应的dp[k-i]就可以了。

代码如下:

class Solution(object):
    def subarraySum(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: int
        """
        dp = [0 for x in nums]
        dp[-1] = nums[-1]
        dic = {}
        dic[dp[-1]] = 1
        for i in xrange(-2,-len(nums)-1,-1):
            dp[i] = dp[i+1] + nums[i]
            if dic.has_key(dp[i]):
                dic[dp[i]] += 1
            else:
                dic[dp[i]] = 1
        res = 0
        for i,v in enumerate(dp):
            if v == k:
                res += 1
            dic[v] -= 1
            if dic.has_key(v-k):
                res += dic[v-k]

        return res