LeetMotion
Given an array of integers nums and an integer k, return the total number of subarrays whose sum equals to k.
A subarray is a contiguous non-empty sequence of elements within an array.
i, compute all subarray sums starting at i. This is O(n²) but works. The key insight: if you know the prefix sum up to each index, you can compute any subarray sum in O(1).prefixSum[i] = nums[0] + nums[1] + ... + nums[i]. The sum of subarray [j+1...i] = prefixSum[i] - prefixSum[j]. So we need: prefixSum[i] - prefixSum[j] = k, which means prefixSum[j] = prefixSum[i] - k.{ prefixSum → count }. For each element, compute the running prefix sum. Check if (prefixSum - k) exists in the map — if so, add its count to the answer. Initialize map with { 0: 1 } to handle subarrays starting from index 0.Banks scan transaction sequences to find windows of time where net deposits equal a suspicious threshold. With millions of transactions, O(n²) is impossible — comparing every pair of time windows would take hours. Prefix sums combined with a hashmap reduce this to O(n): for each transaction, compute the running total, then check in O(1) whether a previous running total exists such that the difference equals the suspicious amount. This is Subarray Sum Equals K running in production, catching fraud in real time.
The simplest approach: for every starting index i, expand the subarray rightward to index j, accumulating the sum. If the running total equals k, increment the count.
i from 0 to n-1.j from i to n-1, accumulating total += nums[j].total == k, increment the counter.Why it's slow: For an array of 20,000 elements, this checks ~200 million subarray pairs. For large inputs it is completely impractical.
def subarraySum(nums, k): count = 0 for i in range(len(nums)): total = 0 for j in range(i, len(nums)): total += nums[j] if total == k: count += 1 return count
Instead of testing all subarrays, we use prefix sums and a hash map to count in a single pass. For each element, we ask: "How many previous prefix sums, when subtracted from the current prefix sum, equal k?"
count = 0, prefSum = 0, and seen = { 0: 1 } (the empty subarray has sum 0, seen once).num in nums, add it to prefSum.need = prefSum - k. This is the prefix sum we'd need to have seen earlier to form a subarray summing to k.need is in seen, add seen[need] to count (each occurrence contributes one valid subarray).prefSum in the map: seen[prefSum] += 1.count.The hash map gives us O(1) lookups, reducing the total time from O(n²) to O(n). Note: because array values can be negative, a sliding window would not work here — prefix sums are the correct approach.
Discussion
…