523. Continuous Subarray Sum
給一個 array nums 和 k，問你 nums 有沒有總合是 k 的倍數的 continuous subarray
這個 subarray 至少要有兩個元素
Example 1:
Input: nums = [23,2,4,6,7], k = 6
Output: true
[2,4] -> 2+4 = 6
Example 2:
Input: nums = [23,2,6,4,7], k = 6
Output: true
[23,2,6,4,7] -> 23+2+6+4+7 = 42
思路:
1.這種算區間總合的應該很直覺能想到用 prefix sum 來記
先對每個 i 算出 presum[i] = nums[0] + nums[1] + ...... + nums[i]
然後就能很輕鬆的用 presum[j] - presum[i] 得出 nums[j+1] + ...... + nums[i]
建 presum 只需 O(n)
2.如果兩層 for-loop iterate i, j 去檢查 (presum[j] - presum[i])%k 等不等於 0
這樣複雜度是 O(n^2) 看測資範圍是不太OK
所以就想有沒有辦法對 j 一次檢查他前面的 i 有沒有能跟他配的
如果 presum[j]%k == 3 那我們就知道前面也要找 presum[i]%k == 3
這樣就代表 (presum[j] - presum[i])%k == 0
那就簡單了 開一個 set 把前面出現過的 presum[i]%k 記起來
後面的 presum[j] 就檢查有沒有模數跟他一樣的
有就能成功配對 沒有就把 presum[j]%k 加進 set 裡給後面的人挑
這樣就只需 iterate 一次
3.題目有另外要求 subarray 至少要有兩個元素
也就是說在檢查 presum[j] 時 presum[j-1] 不能做他的 candidate
那也很簡單 就是檢查完隔一回合再把 presum[j-1] 加進 set 就好
這樣 presum[j-1] 就不會被 presum[j] 挑到
當然也可以改用 dict 然後順便記 index
Python code:
class Solution:
def checkSubarraySum(self, nums: List[int], k: int) -> bool:
n = len(nums)
modset = set()
presum = last = 0
for i in range(n):
presum = (presum + nums[i])%k
if presum in modset:
return True
else:
modset.add(last)
last = presum
return False

大師

大師