LeetCode-560和为 K 的子数组

题目描述

给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的子数组的个数 。

子数组是数组中元素的连续非空序列。

示例 1：

输入：nums = [1,1,1], k = 2
输出：2

示例 2：

输入：nums = [1,2,3], k = 3
输出：2

提示：

• 1 <= nums.length <= 2 * 104
• -1000 <= nums[i] <= 1000
• -107 <= k <= 107

题解

滑动窗口（错解）

未考虑负数的情况

nums = [-1,-1,1] , k = 0出错

class Solution(object):
    def subarraySum(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: int
        """
        ans = 0
        length = len(nums)
        i, j = 0, 0
        sub_sum = nums[0]

        while i < length and j < length and i <= j:
            if sub_sum < k:
                j += 1
                if j < length:
                    sub_sum += nums[j]
            elif sub_sum == k:
                ans += 1
                sub_sum -= nums[i]
                i += 1
                j += 1
                if j < length:                  
                    sub_sum += nums[j]
            else:
                if i < j:
                    sub_sum -= nums[i]
                    i += 1
                elif i == j and j < length-1:
                    sub_sum -= nums[i]
                    i += 1
                    j += 1 
                    sub_sum += nums[j]
                else:
                    break

        return ans

前缀和+哈希

class Solution(object):
    def subarraySum(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: int
        """
        mp = {}
        ans, pre = 0, 0
        for num in nums:
            pre += num
            if pre == k:
                ans += 1
            if pre - k in mp:
                ans += mp[pre-k]
            
            # 前缀和哈希表
            if pre in mp:
                mp[pre] += 1
            else:
                mp[pre] = 1

        return ans