【leetcode刷题】T18-和为K的子数组

今天分享leetcode第18篇文章，也是leetcode第560题—和为K的子数组（Subarray Sum Equals K），地址是：https://leetcode.com/problems/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
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].【中文题目】给定一个整数数组和一个整数 k，你需要找到该数组中和为 k 的连续的子数组的个数。示例 1 :输入:nums = [1,1,1], k = 2
输出: 2 , [1,1] 与 [1,1] 为两种不同的情况。
说明 :数组的长度为 [1, 20,000]。数组中元素的范围是 [-1000, 1000] ，且整数 k 的范围是 [-1e7, 1e7]。【思路】本题和「连续的子数组和」类似，同样可以有两种解法。一是暴力破解，使用数组sums，数组元素sums[i]存储nums数组0->i子数组和，然后循环嵌套遍历存在多少个sums[j] - sums[i]等于k。但是遗憾的是，时间复杂度较高，不能通过测试。二是使用字典（hash），使用字典sums，key为子数组和，value为key出现次数。遍历数组，遇到一个0->i的子数组和tmp_sum，判断其是否在sums中，如果在则增加count相应次数，同时需要增加sums数组中tmp_sum的次数。时间复杂度为O(n)。注意：字典需要默认0出现一次，否则tmp_sum == k时，不能增加count次数。【代码】python版本class Solution(object):
    def subarraySum(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: int
        """
        length = len(nums)
        # 字典存储某个num出现次数，默认0出现1次
        sums = {0:1}
        tmp_sum = 0
        count = 0
        # 统计0->i的元素之和
        for i in range(length):
            tmp_sum += nums[i]
            # tmp_sum == k 或者 tmp_sum - 某个sums[j] == k
            # 都是求 tmp_sum - k 出现次数
            count += sums.get(tmp_sum - k, 0)
            sums[tmp_sum] = sums.get(tmp_sum, 0) + 1
        return count
C++版本class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        map<int, int> sums;
        sums[0] = 1;
        int tmp_sum = 0;
        int count = 0;
        for(int i=0; i < nums.size(); i++){
            tmp_sum += nums[i];
            // tmp_sum == k 或者 tmp_sum - 某个sums[j] == k
            // 都是求 sums[i] - k 出现次数
            if(sums.find(tmp_sum - k) != sums.end())
                count += sums[tmp_sum - k];
            // tmp_sum出现次数+1
            if(sums.find(tmp_sum) == sums.end())
                sums[tmp_sum] = 1;
            else
                sums[tmp_sum] += 1;
        }
        return count;
    }
};