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


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://maksimdan.gitbook.io/interview-practice-problems/leetcode_sessions/523-continuous-subarray-sum.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.