Re: [閒聊] 每日leetcode

[DJYOSHITAKA (franchouchouISBEST)]

523. Continuous Subarray Sum

紀錄prefix sum的餘數
若之前出現過相同餘數的prefix sum
代表這之間的subarray可以被k整除

不過實作起來細節也不少
像是要init mod_hit[0] = -1之類的
WA了幾次
漬漬漬


def checkSubarraySum(self, nums: List[int], k: int) -> bool:
    mod_hit = {}
    mod_hit[0] = -1
    sum_cur = 0

    for idx,i in enumerate(nums):
        sum_cur += i
        if (sum_cur%k) in mod_hit and (idx-mod_hit[sum_cur%k])>=2:
            return True
        elif (sum_cur%k) not in mod_hit:
            mod_hit[sum_cur%k] = idx

    return False

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 125.228.146.144 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1717851545.A.11A.html
→ NTUtriangle: 大師
→ nh60211as: 大師
推 DreaMaker167: 欸我機車行車紀錄器用小蜂鷹 嘎嘎頂
推 sustainer123: 用set()
→ DJYOSHITAKA: 小蜂鷹我研究看看
→ DJYOSHITAKA: 但還是要記index位置吧 能用set嗎
推 sustainer123: 為啥要index?set的值不就前面前綴和的餘數
→ sustainer123: 我們不用知道是哪個區間的前綴和ㄅ?
→ DJYOSHITAKA: 但要知道這個區間長度有沒有>=2
→ DJYOSHITAKA: 喔我知道你的寫法了 你就delay一個loop去記 也可以