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. 1.
The length of the array won't exceed 10,000.
2. 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 - integral_ar`, 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) == False) # needs to be length 2 or more