0560._Subarray_Sum_Equals_K.md

560. Subarray Sum Equals K

难度: Medium

刷题内容

原题连接

• https://leetcode.com/problems/subarray-sum-equals-k/description/

内容描述

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
Note:
The length of the array is in range [1, 20,000].
The range of numbers in the array is [-1000, 1000] and the range of the integer k is [-1e7, 1e7].

解题方案

思路 1

跟two sum一样的题目

就不停维护一个当前和的变量，然后每次都check一下当前和 - k是否在字典里面，如果存在我们就知道了之前有一坨字符串和的值为当前和 - k，然后 当前和的值就是当前和，所以最近接触的一坨字符串其和必为k

例如在[1,2,3,4]里面找7，之前存过1+2在字典里面，然后循环到4的时候当前和为10，就看看3在不在字典里面，一看果然有，那么最近一坨的 3+4 = 7，找到了

但是这里要注意光找到没用，我们要知道存在多少个，所以字典里面的value对应的就是当前和出现的次数

AC 代码：

class Solution(object):
    def subarraySum(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: int
        """
        # 这是为了保证如果当前和的值就等于k的话，我们其实也相当于找到一次
        lookup = {0:1} 
        res = cur_sum = 0
        for num in nums:
            cur_sum += num
            res += lookup.get(cur_sum-k, 0)
            lookup[cur_sum] = lookup.get(cur_sum, 0) + 1
        return res