Comment on page
523 Continuous Subarray Sum
Given a list ofnon-negativenumbers and a targetintegerk, write a function to check if the array has a continuous subarray of size at least 2 that sums up to the multiple ofk, that is, sums up to n*k where n is also aninteger.
Example 1:
Input:
[23, 2, 4, 6, 7], k=6
Output:
True
Explanation:
Because [2, 4] is a continuous subarray of size 2 and sums up to 6.
Example 2:
Input:
[23, 2, 6, 4, 7], k=6
Output:
True
Explanation:
Because [23, 2, 6, 4, 7] is an continuous subarray of size 5 and sums up to 42.
Note:
- 1.The length of the array won't exceed 10,000.
- 2.You may assume the sum of all the numbers is in the range of a signed 32-bit integer.
Current Status: Time Limit Exceeded
The Idea: First I compute an integral array. This always use to find any subsum within the array in O(1) time. For example, the sum within
subarray(1, 3) can be represented in the integral array as integral_ar[0] - integral_ar[3], or the difference in accumulative summations. This can be generalized as integral_ar[max(0, A-1)] - integral_ar[B]. After this point, I brute force check every consecutive sequence with a length greater than 2. I also check for the edge case such as when k = 0, and we have a valid summation array such as [0, 0]Complexity: O(n^2) time, O(n) space
class Solution(object):
def compute_integral_array(self, nums):
"""
:type nums: List[int]
:rtype: List[int]
"""
cum_sum = 0
integral_ar = []
integral_ar.append(0)
for i in nums:
cum_sum += i
integral_ar.append(cum_sum)
return integral_ar
def checkSubarraySum(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: bool
"""
integral_ar = self.compute_integral_array(nums)
i = 0
j = i + 1
while i < len(integral_ar):
j = i + 2
while j < len(integral_ar):
bound_check = max(0, i)
sub_sum = integral_ar[j] - integral_ar[bound_check]
if not sub_sum and not k:
return True
elif k and sub_sum % k == 0:
return True
j += 1
i += 1
return False
Some testing
obj = Solution()
assert(obj.checkSubarraySum([1,2,3], 5) == True)
assert(obj.checkSubarraySum([23,2,6,4,7], 0) == False)
assert(obj.checkSubarraySum([23, 2, 6, 4, 7], 6) == True)
assert(obj.checkSubarraySum([23, 2, 4, 6, 7], 6) == True)
assert(obj.checkSubarraySum([1,1,1], 4) == False)
assert(obj.checkSubarraySum([1,2,3,4], 10) == True)
assert(obj.checkSubarraySum([1,2,3,4], 11) == False)
assert(obj.checkSubarraySum([], 0) == False) # needs to be length 2 or more
assert(obj.checkSubarraySum([1,2], 3) == True)
assert(obj.checkSubarraySum([1], 1) == False) # needs to be length 2 or more
Last modified 4yr ago