Re: [閒聊] 每日leetcode

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

1590. Make Sum Divisible by P

給一個正整數array nums

請移除長度最短的subarray(可以是空矩陣)

讓剩下的元素總和可以被p整除

如果無法達成則回傳p

否則回傳subarray的長度

思路:

首先我們先計算nums的總和sum

sum % p =remainder

如果remainder == 0，就回傳0

不然我們就要去找一段subarray，該subarray % p =remainder

紀錄nums[0]+nums[1]+...+nums[i]%p的值(remainder_i)，0 <= i < len(nums)

接著找到j 使nums[j+1]+nums[j+2]...+nums[i] % p ==remainder，0<= j < len(nums)

要怎麼找到j

就用一個hash table去紀錄每個餘數最新出現的index

x = (remainder_i - remainder + p ) % p

去找x在前面有沒有出現過

有出現的話

ans = min(ans, i-hash_map[x])

接著更新hash_map裡remainder_i的index

就這樣一直找完整個矩陣

就可以得到答案

golang code :

func minSubarray(nums []int, p int) int {

        sum, res, prev,n := 0, math.MaxInt64, 0,len(nums)
        rec := make(map[int]int)
        for _, val := range nums {
                sum += val
        }
        remainder := sum % p
        if remainder == 0 {
                return 0
        }
        rec[0] = -1
        for key, val := range nums {
                prev = (prev + val) % p
                idx := (prev - remainder + p) % p
                if last, ok := rec[idx]; ok {
                        res = min(res, key-last)
                }
                rec[prev] = key
        }
        if res < n {
                return res
        }
        return -1
}

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 42.72.187.88 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1727932795.A.388.html
推 DJYOSHITAKA: 捲三小
→ sustainer123: 卷三小