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