Untitled

from collections import defaultdict

class Solution:
    def subarraySum_brute(self, nums: List[int], k: int) -> int:
        """O(n**2) brute force"""

        num_matching = 0
        for sequence_start_index in range(0, len(nums)):
            for sequence_end_index in range(sequence_start_index + 1, len(nums) + 1):
                if sum(nums[sequence_start_index:sequence_end_index]) == k:
                    num_matching += 1
        return num_matching

    def subarraySum(self, nums: List[int], k: int) -> int:
        """Optimized, memory for CPU.
        
        Precompute index to end sum for each ends O(n) (2x O(n)) (could be n^2 with brute force approach)

        input [1, 1, 4, -3, 2], k = 2

        sum from left: [1, 2, 6, 3, 5]
        sum from right: [2, -1, 3, 4, 5]

        sum(i,j) say sum(1,3) would be the same as sum(1,3) - sum(0,1)


        [1, 1, 4, -3, 2]

        grab [1, 4, -3] out of the middle via [1, 1, 4, -3] : sum(0,3) then subtract sum(0,1) so sum(1,3) = sum(0,3) - sum(0,1)

        Becuase sum(0,3) and sum(0,1) are lookups, any sum(0,n) is an O(1) lookup, then doing two of them is 2x O(1)

        Can we then make another mapping that is from what the sum is to the number of sums it has? {sum: num_of_this_sum_occurence}. Also O(n) to create

        Then using that, we can step through the keys checking if the number to make the sum we're looking for is available and how many times we can create it (the minimum of the amounts)

        Trying it:

        nums = [1, 1, 4, -3, 2], k = 2

        sum(0,i) map: [1, 2, 6, 3, 5]

        sum_frequency_map = {
            1: 1, 
            2: 1, 
            6: 1,
            3: 1,
            5: 1
        }


        stepping through sum frequency keys, I see a 1. Need a -1 to meet k=2 if that's available, look up attempt => not available
        See a 2, need nothing to match, count is now at 1

        See a 6, need a 4 to subtract, no 4, count is at 1

        See a 3, need a 1 to subtract, one 1, count is at 2

        See a 5, need a 3 to subtract, one 3, count is at 3

        """
        count_of_matching_subarrays = 0

        # Make precomputed sum(0,i) lookup
        lookup_sub_sum_from_left = dict()
        subsum = 0
        for i, num in enumerate(nums):
            subsum += num
            lookup_sub_sum_from_left[i] = subsum
    
    
        # Use precompute to make another precomputed frequency map
        sum_frequencies = defaultdict(lambda: 0)
        for _, sumvalue in lookup_sub_sum_from_left.items():
            sum_frequencies[sumvalue] += 1

        
        # Use the frequency map to look up compatible subarrays
        for sumvalue, frequency in sum_frequencies.items():
            if sumvalue == k:
                count_of_matching_subarrays += frequency
            else:
                matching_frequency = sum_frequencies.get(sumvalue - k, 0)  # k = matching_sub_sum - sumvalue
                count_of_matching_subarrays += min(matching_frequency, frequency)


        return count_of_matching_subarrays

        """
        Trace solution to see if it's doing what I'd like it to do

        input = [1,5,1,-1,1], k = 6, correct answer is 3

        (just realized this doesn't have to be a dict, a list can be "looked up" by index)
        lookup_sub_sum_from_left = {
          1, 6, 7, 6, 7
        }
        sum_frequencies = {
            1: 1
            6: 2
            7: 2
        }
        
        Check 1, lookup -5 = 1-6, no lookup, move on, count still 0
        Check 6, matches add 2 to count, count is 2
        Check 7, lookup 1 = 7-6, 1 found. Min of (1,2) is 1, add 1 to count, count is 3
        Looks good
        """