Re: [閒聊] 每日leetcode

[dont (dont)]

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
推 sustainer123: 大師