<p>Given an array of integers <code>nums</code> and an integer <code>k</code>, return <em>the total number of subarrays whose sum equals to</em> <code>k</code>.</p>

<p>A subarray is a contiguous <strong>non-empty</strong> sequence of elements within an array.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<pre><strong>Input:</strong> nums = [1,1,1], k = 2
<strong>Output:</strong> 2
</pre><p><strong class="example">Example 2:</strong></p>
<pre><strong>Input:</strong> nums = [1,2,3], k = 3
<strong>Output:</strong> 2
</pre>
<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= nums.length &lt;= 2 * 10<sup>4</sup></code></li>
	<li><code>-1000 &lt;= nums[i] &lt;= 1000</code></li>
	<li><code>-10<sup>7</sup> &lt;= k &lt;= 10<sup>7</sup></code></li>
</ul>

"""
1 1 1 k = 2
=
1 1, 1 1 
return 2

1 2 3   k = 3
1 2, 3
return 2

-5 0 5 k = 0
-5,5
0
return 2

1 2 3 -6 1 k = 1
1 3 6  0 1
  ^    ^
         i
    j
return 2

1 6 3  -2  -1 1     k = 1
1 7 10  8   7 8
     ^ 
               ^

1 2 3 4  5   10   20
1 3 6 10 15  25   45
key is that it must be CONTINUGOUS.
"""
class Solution:
    def subarraySumBinarySearch(self, nums: List[int], k: int) -> int:
        # from prefixSumToIndex
        hm = defaultdict(lambda:[])
        # you can always remove no elements from the left.
        hm[0].append(-1)

        for i in range(0, len(nums)):
            prev = nums[i-1] if i - 1 >= 0 else 0
            nums[i] = prev + nums[i]
            hm[nums[i]].append(i)

        result = 0
        for i in range(0, len(nums)):
            # How many complements are to the left? prefixSum[i] - complement = k
            complement = nums[i] - k
            # returns the number of indicies LESS than i
            result += self.binarySearch(i, hm[complement])
        return result

    # returns the right most value less than target
    def binarySearch(self, target, nums):
        if not nums:
            return 0

        L, R = 0, len(nums) - 1
        result = 0
        while L <= R:
            M = (L+R)//2
            if nums[M] < target:
                result = M
                L = M + 1
            else: # nums[M] >= target:
                R = M - 1
        if target <= nums[result]:
            return 0
        else:
            return result + 1


    def subarraySum(self, nums: List[int], k: int) -> int:
        result = 0
        
        # counts the number of elements with this prefix sum value so far.
        hm = defaultdict(lambda:0)

        # there's 1 subarray you can make that removes 0 elements.
        hm[0] = 1

        for i in range(0, len(nums)):
            prev = nums[i-1] if i > 0 else 0
            nums[i] = prev + nums[i]
            # look for complement. prefixSum[i] - prefixSum[j] = k. Look for existence of prefixSum[j]
            search =  nums[i] - k
            # incr result with number of j's that would form a subsetsum = k
            result += hm[search]
            
            # update hm to show that there's another prefix sum at that sum. 
            hm[nums[i]] += 1
        
        return result









20200