<p>Given an integer array nums and an integer k, return <code>true</code> <em>if </em><code>nums</code><em> has a <strong>good subarray</strong> or </em><code>false</code><em> otherwise</em>.</p>

<p>A <strong>good subarray</strong> is a subarray where:</p>

<ul>
	<li>its length is <strong>at least two</strong>, and</li>
	<li>the sum of the elements of the subarray is a multiple of <code>k</code>.</li>
</ul>

<p><strong>Note</strong> that:</p>

<ul>
	<li>A <strong>subarray</strong> is a contiguous part of the array.</li>
	<li>An integer <code>x</code> is a multiple of <code>k</code> if there exists an integer <code>n</code> such that <code>x = n * k</code>. <code>0</code> is <strong>always</strong> a multiple of <code>k</code>.</li>
</ul>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> nums = [23,<u>2,4</u>,6,7], k = 6
<strong>Output:</strong> true
<strong>Explanation:</strong> [2, 4] is a continuous subarray of size 2 whose elements sum up to 6.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> nums = [<u>23,2,6,4,7</u>], k = 6
<strong>Output:</strong> true
<strong>Explanation:</strong> [23, 2, 6, 4, 7] is an continuous subarray of size 5 whose elements sum up to 42.
42 is a multiple of 6 because 42 = 7 * 6 and 7 is an integer.
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> nums = [23,2,6,4,7], k = 13
<strong>Output:</strong> false
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= nums.length &lt;= 10<sup>5</sup></code></li>
	<li><code>0 &lt;= nums[i] &lt;= 10<sup>9</sup></code></li>
	<li><code>0 &lt;= sum(nums[i]) &lt;= 2<sup>31</sup> - 1</code></li>
	<li><code>1 &lt;= k &lt;= 2<sup>31</sup> - 1</code></li>
</ul>

class Solution:
    def checkSubarraySum(self, nums: List[int], k: int) -> bool:
        def rf(ls):
            if len(ls) == 1:
                return False

            m = (0 + len(ls) - 1) // 2
            nextm = m + 1
            # blocks 0 .. m, m + 1 .. len(ls) - 1

            sums = set()
            i = m
            sm = 0
            while i >= 0:
                sm = (sm + ls[i]) % k
                sums.add(k - sm if sm != 0 else 0)
                i -= 1
            
            i = nextm
            sm = 0
            while i < len(ls):
                sm = (sm + ls[i]) % k
                if (sm % k) in sums:
                    return True
                i += 1
            
            ltrue = rf(ls[:m+1])
            if ltrue:
                return True
            rtrue = rf(ls[m+1:])
            if rtrue:
                return True
            
            return False
        
        def ap2(nums):
            rhm = dict()

            i = len(nums) -1
            s = 0
            while i >= 0:
                s = (s + nums[i]) % k
                if s not in rhm:
                    rhm[s] = i
                i -= 1
            rhm[0] = len(nums)
            allsum = s

            # -1 Iteration        
            if allsum in rhm and rhm[allsum] > 1:
                return True

            i = 0
            s = 0
            while i < len(nums) - 1:
                s = (s + nums[i]) % k
                tosearch = (allsum - s) % k
                if tosearch not in rhm:
                    i += 1
                    continue
                
                if rhm[tosearch] > i + 2:
                    return True

                i += 1
            
            return False
        
        def ap3(nums):
            prefixmod = 0
            modseen = dict()
            modseen[0] = -1

            for i, n in enumerate(nums):
                prefixmod = (prefixmod + n) % k
                if prefixmod in modseen:
                    leftindx = modseen[prefixmod]
                    if (leftindx + 1) < i:
                        return True
                else:
                    modseen[prefixmod] = i
            
            return False

        
        apr = 1
        if apr == 1:
            return rf(nums)
        elif apr == 2:
            return ap2(nums)
        elif apr == 3:
            return ap3(nums)


       



      
            


                








30600