Input: nums = [1,1,1], k = 2
Output: 2

Input: nums = [1,2,3], k = 3
Output: 2

Solution Explanation: Subarray Sum Equals K

This problem asks us to find the total number of subarrays within a given array nums whose elements sum up to a target value k. A brute-force approach would involve checking every possible subarray, resulting in O(n²) time complexity. However, a more efficient solution utilizes the concept of prefix sums and a hash table.

Approach:

1. Prefix Sum: We calculate the prefix sum of the array nums. The prefix sum at index i represents the sum of all elements from index 0 to i. This allows us to efficiently calculate the sum of any subarray: the sum of a subarray from index i to j is simply prefixSum[j] - prefixSum[i-1].

2. Hash Table: We use a hash table (dictionary in Python, HashMap in Java, etc.) to store the frequency of each prefix sum encountered so far. The key is the prefix sum, and the value is its count. We initialize the hash table with prefixSum[0] = 0 and its count as 1 (representing the empty subarray).

3. Iteration: We iterate through the array:

   • For each element, we update the current prefix sum s.
   • We check if s - k exists as a key in the hash table. If it does, it means there's a previous prefix sum whose difference with the current prefix sum is exactly k. This indicates a subarray with sum k exists. We add the count of s - k to our answer.
   • We update the count of the current prefix sum s in the hash table.

Time Complexity Analysis:

The algorithm iterates through the array nums once. All hash table operations (insertion, lookup) take O(1) on average. Therefore, the overall time complexity is O(n), where n is the length of nums.

Space Complexity Analysis:

The space complexity is determined by the size of the hash table. In the worst case, the hash table could store all prefix sums, resulting in O(n) space complexity.

Code Examples:

The provided code examples in Python, Java, C++, Go, TypeScript and Rust all implement this approach. They differ slightly in syntax and data structure implementations (e.g., Counter in Python vs. HashMap in Java), but the core logic remains the same. The comments within the code further clarify each step.

Example Walkthrough (Python):

Let's trace the Python example with nums = [1, 1, 1] and k = 2:

• Initially, cnt = {0: 1}, ans = 0, s = 0.
• Iteration 1: x = 1, s = 1, ans += cnt[1 - 2] (which is 0), cnt = {0: 1, 1: 1}.
• Iteration 2: x = 1, s = 2, ans += cnt[2 - 2] = cnt[0] = 1, cnt = {0: 1, 1: 1, 2: 1}.
• Iteration 3: x = 1, s = 3, ans += cnt[3 - 2] = cnt[1] = 1, cnt = {0: 1, 1: 1, 2: 1, 3: 1}.
• Finally, ans = 2, which is the correct answer.

This efficient approach using prefix sums and a hash table provides a significant performance improvement over a brute-force solution, making it suitable for handling larger input arrays.