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 updated