https://leetcode.com/problems/continuous-subarray-sum
523. Continuous Subarray Sum
給定一數列nums與整數k
假如nums的子序列符合以下條件:
1 長度不小於2
2 子序列的和為k的倍數
請回傳true 反之false
Example 1:
Input: nums = [23,2,4,6,7], k = 6
Output: true
Explanation: [2, 4] is a continuous subarray of size 2 whose elements sum up
to 6.
Example 2:
Input: nums = [23,2,6,4,7], k = 6
Output: true
Explanation: [23, 2, 6, 4, 7] is an continuous subarray of size 5 whose
elements sum up to 42.
42 is a multiple of 6 because 42 = 7 * 6 and 7 is an integer.
Example 3:
Input: nums = [23,2,6,4,7], k = 13
Output: false
Constraints:
1 <= nums.length <= 105
0 <= nums[i] <= 109
0 <= sum(nums[i]) <= 231 - 1
1 <= k <= 231 - 1
思路:
我第一個念頭是backtracking 但看到條件就知道一定不行
之後改用前綴和
設p[i] = (nums[i] + nums[i-1] +.......+ nums[0])%k
區間[i,j]符合題目要求就代表p[i-1]跟p[j]相等
以例一來說:
p[0] = 5
p[1] = 1
p[2] = 5
區間[1,2]符合題目要求 因為p[0] = nums[0] p[2] = nums[2] + nums[1] + nums[0]
p[2] - p[0] = nums[1] + nums[2] = 0
相加餘數為零 所以[1,2]符合題目要求
Python Code:
def checkSubarraySum(self, nums: List[int], k: int) -> bool:
nums[0] %= k
d = set()
d.add(0)
for i in range(1,len(nums)):
nums[i] = (nums[i]+nums[i-1])%k
if nums[i] in d:
return True
d.add(nums[i-1])
return False