# 523 Continuous Subarray Sum

Given a list of**non-negative**numbers and a target**integer**k, write a function to check if the array has a continuous subarray of size at least 2 that sums up to the multiple of**k**, that is, sums up to n\*k where n is also an**integer**.

**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

```python
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

```python
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
```