Re: [閒聊] 每日leetcode
1590. Make Sum Divisible by P
## 思路
先算總和mod p的差值diff
目標是刪掉差值的最短subarray
用HashTable更新 PrefixSum % p的 idx
如果目前idx是prefix,
subarray就會是 idx - last_idx[prefix-diff]
## Code
```python
class Solution:
def minSubarray(self, nums: List[int], p: int) -> int:
diff = sum(nums) % p
if diff == 0:
return 0
res = len(nums)
last_idx = {0: -1}
prefix = 0
for idx, num in enumerate(nums):
prefix = (prefix + num) % p
target = (prefix - diff) % p
if target in last_idx:
res = min(res, idx - last_idx[target])
last_idx[prefix] = idx
return res if res < len(nums) else -1
```
--
https://i.imgur.com/kyBhy6o.jpeg
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 185.213.82.56 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1727915833.A.95F.html
推
10/03 08:45,
1年前
, 1F
10/03 08:45, 1F
討論串 (同標題文章)
完整討論串 (本文為第 935 之 1548 篇)：