Practice/Meta/Leetcode 560. Subarray Sum Equals K

Leetcode 560. Subarray Sum Equals K

CodingMust

Problem

Given an array of integers and a target sum value, determine how many contiguous subarrays within the array sum exactly to the target value.

A subarray is a continuous portion of the array. For example, in the array [1, 2, 3], valid subarrays include [1], [2], [3], [1, 2], [2, 3], and [1, 2, 3].

Requirements

1. Count all contiguous subarrays whose elements sum to exactly k
2. Handle arrays containing negative numbers, zero, and positive numbers
3. Return the total count of matching subarrays
4. Each unique subarray should be counted once (different positions of the same values count separately)

Constraints

• 1 ≤ nums.length ≤ 20,000
• -1000 ≤ nums[i] ≤ 1000
• -10^7 ≤ k ≤ 10^7
• Target time complexity: O(n)
• Target space complexity: O(n)

Examples

Example 1:

Input: nums = [1, 2, 3, 4], k = 5 Output: 2 Explanation: The subarrays [2, 3] and [1, 4] both sum to 5

Example 2:

` Input: nums = [1, -1, 1, -1, 1], k = 0 Output: 4 Explanation: Multiple subarrays sum to 0:

• [1, -1] (starting at index 0)
• [-1, 1] (starting at index 1)
• [1, -1, 1, -1] (starting at index 0)
• [-1, 1, -1, 1] (starting at index 1) `

Example 3:

Input: nums = [3, 5, 2, 7], k = 7 Output: 2 Explanation: Subarrays [7] (single element) and [5, 2] both sum to 7