Re: [閒聊] 每日leetcode

[JIWP (神楽めあ的錢包)]

每日連續200天了，好耶

523. Continuous Subarray Sum

給一個整數array nums和一個整數k

請判斷nums是否包含good subarray

subarray的定義

(1)至少有兩個元素

(2)subarray的合是k的倍數

思路:

如果有兩個數a、b，除以k的餘數相等則(a-b)%k==0

所以用prefix sum的概念

用sum記錄到目前為止所有元素的總和

並且用一個hash table紀錄sum%k第一次出現的index

如果目前sum%k在之前已經出現過且index相差2以上就回傳true

golang code:

func checkSubarraySum(nums []int, k int) bool {
    if len(nums) < 2 {
        return false
    }
    modMap, sum := make(map[int]int), 0
    modMap[0] = -1
    for i, num := range nums {
        sum += num
        mod := sum % k
        if prevIndex, exists := modMap[mod]; exists {
            if i - prevIndex >= 2 {
                return true
            }
        } else {
            modMap[mod] = i
        }
    }
    return false
}

--
https://i.imgur.com/r9FBAGO.gif

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 223.139.255.78 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1717848442.A.6B7.html
推 sustainer123: 好猛 大師
→ sustainer123: 你還差多少錢才能換衣服
推 Che31128: 大師
推 aioiwer318: 別卷了
→ JIWP: 沒打周賽，點數賺很慢
→ JIWP: 我現在才3229
推 CanIndulgeMe: 卷不動了......