Leetcode 560:和为K的子数组(超详细的解法!!!)
in leetcode with 0 comment

Leetcode 560:和为K的子数组(超详细的解法!!!)

in leetcode with 0 comment

给定一个整数数组和一个整数 k,你需要找到该数组中和为 k 的连续的子数组的个数。

示例 1 :

输入:nums = [1,1,1], k = 2
输出: 2 , [1,1] 与 [1,1] 为两种不同的情况。

说明 :

  1. 数组的长度为 [1, 20,000]。
  2. 数组中元素的范围是 [-1000, 1000] ,且整数 k 的范围是 [-1e7, 1e7]。

解题思路

首先想到的解法就是暴力解法,使用三重循环。

class Solution:
    def subarraySum(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: int
        """
        nums_len, result = len(nums), 0
        for i in range(nums_len):
            for j in range(i, nums_len):
                cur_sum = 0
                for l in range(i, j + 1):
                    cur_sum += nums[l]

                if cur_sum == k:
                    result += 1

        return result

上面这种做法显然没有什么参考价值。所以我们思考有没有O(n^2)的解法。同样非常容易想到,我们每次计算[i,len(nums)]这个区间内以i开始的每个小区间的和,记录所以和为k的区间个数。通过遍历nums每个元素i,我们就可以求解出每个以i开始并且和为k的区间个数,最后加在一起即可。

class Solution:
    def subarraySum(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: int
        """
        nums_len, result = len(nums), 0
        for i in range(nums_len):
            cur_sum = 0
            for j in range(i, nums_len):
                cur_sum += nums[j]
                if cur_sum == k:
                    result += 1
                
        return result

有没有更快的办法。有,这个问题可以通过Prefix sum来求解。假设我们令P[i] = A[0] + A[1] + ... + A[i-1]P[j] = A[0] + A[1] + ... + A[j-1],那么P[j] - P[i] = A[i] + A[i+1] + ... + A[j-1]。如果P[j] - P[i] == S的话,那么[i,j]就是我们需要的区间。所以我们对于每个j,我们只要计算有多少个i使得P[j] - P[i] == S,这样我们就得到了P[j]作为右区间并且和为S的区间数。对于A中的每个元素都做同样的处理,最有将所有的结果相加即可。

具体实现上,我们通过hash_map记录P[j]。初始化的时候要注意一个细节,对于dict[0]=1。为什么?因为当P[j]==S时,P[i]=0并且此时我们的result=1

class Solution:
    def subarraySum(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: int
        """
        result, cur_sum = 0, 0
        sum_dict = {0:1}
        for num in nums:
            cur_sum += num
            if cur_sum - k in sum_dict:
                result += sum_dict[cur_sum - k]
            sum_dict[cur_sum] = sum_dict.get(cur_sum, 0) + 1
                
        return result

我将该问题的其他语言版本添加到了我的GitHub Leetcode

如有问题,希望大家指出!!!

「如果我的文章对你有很大帮助,那么不妨~!」

coordinate

谢谢老板O(∩_∩)O~

使用微信扫描二维码完成支付

Responses