560. 和为K的子数组 [medium]

560. 和为K的子数组 [medium]

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

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

示例 1 :

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

说明 :

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

通过次数65,434 | 提交次数145,982

Second Try [golang]

2020-08-17

前缀和的练习，每次考察在该位置前面有多少个连续子序列可凑成target目标，一遍构建前缀和一遍得到结果。

func subarraySum(nums []int, k int) int {
    preSum := make(map[int]int)
    preSum[0] = 1 // 不然preSum[j] - preSum[i],怎么都得不到第一个nums[0]的数值
    currSum := 0
    counter := 0 
    for _, n := range(nums) {
        currSum += n 
        counter += preSum[currSum - k]
        preSum[currSum] += 1
    }
    return counter 
}

• 执行用时：28 ms, 在所有 Go 提交中击败了74.64%的用户
• 内存消耗：6.3 MB, 在所有 Go 提交中击败了29.73%的用户

First Try [golang]

2020-08-17

用列表构建完前缀和才来进行遍历查找，复杂度是O(N^2)了，比不上Second Try用map一遍构建一个遍查O(N)的复杂度。

func subarraySum(nums []int, k int) int {
    preSum := make([]int, len(nums) + 1) 
    preSum[0] = 0 
    counter := 0 
    for idx, n := range(nums) {
        preSum[idx + 1] = preSum[idx] + n 
    }
    for i := 0; i< len(preSum); i++ {
        for j:= i + 1; j < len(preSum); j++ {
            if preSum[j] - preSum[i] == k {
                counter += 1
            }
        }
    }
    return counter 
}

• 执行用时：372 ms, 在所有 Go 提交中击败了19.92%的用户
• 内存消耗：5.8 MB, 在所有 Go 提交中击败了100.00%的用户