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