C/C++教程

LeetCode 560 和为 K 的子数组

本文主要是介绍LeetCode 560 和为 K 的子数组,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

群里看到有人面微软的一面题。

第一种方式,暴力解,二重循环查找sum=k的。

第二种方式,刚看了题解也还是有点晕,主要思路就是前缀和+哈希表。重点是一次循环,边统计当前下标的前缀和 边查找符合要求的前缀和是否已经出现过,并且将出现的次数加到ans中。

第一种方式。

func subarraySum(nums []int, k int) int {
    ans := 0
    for left:=0;left<len(nums);left++ {
        sum :=0
        for right:=left;right>=0;right-- {
            sum+=nums[right]
            if sum==k {
                ans++
            }
        }
    }

    return ans
}

  第二种方式。

func subarraySum(nums []int, k int) int {
    ans := 0
    preSum := 0
    m := make(map[int]int, 0)
    m[0]=1
    for _, num := range nums {
        preSum+=num
        ans+=m[preSum-k]
        m[preSum]++
    }

    return ans
}

  

这篇关于LeetCode 560 和为 K 的子数组的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!