Untitled
unknown
python
2 months ago
3.7 kB
10
Indexable
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 """
Editor is loading...
Leave a Comment