continuous_subarray_sum

View Source

 1# @leet start
 2class Solution:
 3    def checkSubarraySum(self, nums: list[int], k: int) -> bool:
 4        """
 5        This question asks us to find a subarray, where the length is at least 2,
 6        and the sum of the elements in the aubarray is a multiple of k.
 7
 8        We can do this in $O(n^3)$ time by finding the sums of all the subarrays
 9        and checking them. This solution finds this in $O(n)$ time.
10
11        We iterate once through the array, keeping track of the prefix modulus
12        of the array. If we have seen the same prefix modulus before, we make
13        sure we saw it at least an index of at least 1 away, so the length of
14        the subarray is 2.
15        """
16        prefix_mod = 0
17        mod_seen = {}
18
19        for i, num in enumerate([0] + nums):
20            prefix_mod = (prefix_mod + num) % k
21
22            if prefix_mod in mod_seen:
23                if i - mod_seen[prefix_mod] > 1:
24                    return True
25            else:
26                mod_seen[prefix_mod] = i
27
28        return False
29
30
31# @leet end
32
33
34def test():
35    assert 2 + 2 == 4

class Solution: View Source

 3class Solution:
 4    def checkSubarraySum(self, nums: list[int], k: int) -> bool:
 5        """
 6        This question asks us to find a subarray, where the length is at least 2,
 7        and the sum of the elements in the aubarray is a multiple of k.
 8
 9        We can do this in $O(n^3)$ time by finding the sums of all the subarrays
10        and checking them. This solution finds this in $O(n)$ time.
11
12        We iterate once through the array, keeping track of the prefix modulus
13        of the array. If we have seen the same prefix modulus before, we make
14        sure we saw it at least an index of at least 1 away, so the length of
15        the subarray is 2.
16        """
17        prefix_mod = 0
18        mod_seen = {}
19
20        for i, num in enumerate([0] + nums):
21            prefix_mod = (prefix_mod + num) % k
22
23            if prefix_mod in mod_seen:
24                if i - mod_seen[prefix_mod] > 1:
25                    return True
26            else:
27                mod_seen[prefix_mod] = i
28
29        return False

def checkSubarraySum(self, nums: list[int], k: int) -> bool: View Source

 4    def checkSubarraySum(self, nums: list[int], k: int) -> bool:
 5        """
 6        This question asks us to find a subarray, where the length is at least 2,
 7        and the sum of the elements in the aubarray is a multiple of k.
 8
 9        We can do this in $O(n^3)$ time by finding the sums of all the subarrays
10        and checking them. This solution finds this in $O(n)$ time.
11
12        We iterate once through the array, keeping track of the prefix modulus
13        of the array. If we have seen the same prefix modulus before, we make
14        sure we saw it at least an index of at least 1 away, so the length of
15        the subarray is 2.
16        """
17        prefix_mod = 0
18        mod_seen = {}
19
20        for i, num in enumerate([0] + nums):
21            prefix_mod = (prefix_mod + num) % k
22
23            if prefix_mod in mod_seen:
24                if i - mod_seen[prefix_mod] > 1:
25                    return True
26            else:
27                mod_seen[prefix_mod] = i
28
29        return False

This question asks us to find a subarray, where the length is at least 2, and the sum of the elements in the aubarray is a multiple of k.

We can do this in $O(n^3)$ time by finding the sums of all the subarrays and checking them. This solution finds this in $O(n)$ time.

We iterate once through the array, keeping track of the prefix modulus of the array. If we have seen the same prefix modulus before, we make sure we saw it at least an index of at least 1 away, so the length of the subarray is 2.

def test(): View Source

35def test():
36    assert 2 + 2 == 4