Documentation Index
Fetch the complete documentation index at: /llms.txt
Use this file to discover all available pages before exploring further.
Tested Python solution for LeetCode 560 with 15 pytest cases. Generate a practice environment with lcpy.
lcpy gen -n 560 # by problem number
lcpy gen -s subarray_sum_equals_k # by problem name
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.
Input: nums = [1,1,1], k = 2
Output: 2
Input: nums = [1,2,3], k = 3
Output: 2
from collections import defaultdict
class Solution:
# Time: O(n)
# Space: O(n)
def subarray_sum(self, nums: list[int], k: int) -> int:
prefix_sum_counts = defaultdict(int)
prefix_sum_counts[0] = 1
current_sum = 0
count = 0
for num in nums:
current_sum += num
if current_sum - k in prefix_sum_counts:
count += prefix_sum_counts[current_sum - k]
prefix_sum_counts[current_sum] += 1
return count
| Time | Space |
|---|---|
| O(n) | O(n) |