function subarraySum(nums, k) {
if (nums.length === 0) return 0;
let count = 0;
for (let i = 0; i < nums.length; i++) {
let currentSum = 0;
for (let j = i; j < nums.length; j++) {
currentSum += nums[j];
if (currentSum === k) {
count++;
}
}
}
return count;
}
if (require.main === module) {
console.log(subarraySum([1,1,1], 2));
console.log(subarraySum([1,2,3], 3));
console.log(subarraySum([1,-1,0], 0));
console.log(subarraySum([], 0));
console.log(subarraySum([0], 0));
}
// File: javascript.brute.js
// Brute-force Subarray Sum Equals K
// O(n^2) time, O(1) extra space (n = nums.length)
/**
* Brute-force approach: Iterate over all possible subarrays and compute their sums.
* For each starting index i, accumulate sum from i to j and check if it equals k.
* This ensures correctness but is inefficient for large n due to quadratic time.
*
* Why this solution:
* - It directly checks every contiguous subarray, guaranteeing we count all valid ones.
* - No additional data structures needed, simple to implement and understand.
*
* Where to use:
* - Small arrays (n <= 1000) or to demonstrate baseline correctness in interviews.
* - When optimizing for space over time.
*
* Complexity:
* - Time: O(n^2) - Two nested loops: outer for start, inner for end, summing in O(1) per step with accumulation.
* - Space: O(1) - Only a few variables for sum and count.
*
* Interview notes:
* - Start with this in interviews to show you understand the problem definition.
* - Explain why it's slow: for n=2e4, it does ~2e8 operations, which may timeout.
* - Transition to optimized prefix sum approach for better performance.
* - Handles negatives/zeros correctly since it recomputes sums each time.
*
* Edge cases handled:
* - Empty array: loops don't run, count=0.
* - Single element: checked if nums[0] === k.
* - All zeros, k=0: counts all non-empty subarrays.
*
* @param {number[]} nums - the input array of integers
* @param {number} k - the target sum
* @returns {number} the count of subarrays with sum equal to k
*/
function subarraySum(nums, k) {
if (nums.length === 0) return 0; // Early return for empty array
let count = 0;
for (let i = 0; i < nums.length; i++) { // Outer loop: start of subarray
let currentSum = 0; // Reset sum for each new start
for (let j = i; j < nums.length; j++) { // Inner loop: end of subarray
currentSum += nums[j]; // Accumulate sum incrementally (O(1) per addition)
if (currentSum === k) { // Check after each addition
count++; // Increment if match found
}
}
}
return count;
}
// Test runner for Node.js environment
if (require.main === module) {
console.log(subarraySum([1,1,1], 2)); // 2
console.log(subarraySum([1,2,3], 3)); // 2
console.log(subarraySum([1,-1,0], 0)); // 2
console.log(subarraySum([], 0)); // 0
console.log(subarraySum([0], 0)); // 1
}
function subarraySum(nums, k) {
const prefixMap = new Map();
prefixMap.set(0, 1);
let prefixSum = 0;
let count = 0;
for (let i = 0; i < nums.length; i++) {
prefixSum += nums[i];
if (prefixMap.has(prefixSum - k)) {
count += prefixMap.get(prefixSum - k);
}
prefixMap.set(prefixSum, (prefixMap.get(prefixSum) || 0) + 1);
}
return count;
}
if (require.main === module) {
console.log(subarraySum([1,1,1], 2));
console.log(subarraySum([1,2,3], 3));
console.log(subarraySum([1,-1,0], 0));
console.log(subarraySum([], 0));
console.log(subarraySum([0], 0));
}
// File: javascript.optimized.js
// Optimized Subarray Sum Equals K using Prefix Sum and Hash Map
// O(n) time average, O(n) space
/**
* Optimized approach: Use prefix sums to represent cumulative sum up to each index.
* Maintain a hash map of prefixSum -> frequency.
* For each index, check if (currentPrefix - k) exists in map, adding its frequency to count.
* Update map after check to avoid invalid self-counts.
*
* Why this solution:
* - Prefix sums allow O(1) subarray sum computation via subtraction.
* - Hash map enables O(1) lookups for previous prefixes where difference == k.
* - Handles negative numbers and zeros seamlessly, unlike sliding window.
*
* Where to use:
* - Large arrays (up to 2e4) as per constraints, efficient in time.
* - When counting all subarrays with exact sum is needed.
*
* Complexity:
* - Time: O(n) - Single pass through array, each operation (add, check, update) is O(1) amortized.
* - Space: O(n) - Hash map can store up to n unique prefix sums in worst case.
*
* Interview notes:
* - Explain prefix sum concept: sum[i..j] = prefix[j] - prefix[i-1].
* - Highlight initializing map with {0:1} for subarrays starting at index 0.
* - Discuss why order matters: check before update to prevent counting current prefix incorrectly.
* - Compare to brute: from O(n^2) to O(n), big win for large n.
* - In JS, use Map for safe handling of negative/large keys (unlike object {}).
*
* Edge cases handled:
* - Empty array: loop doesn't run, count=0.
* - k=0: correctly counts subarrays summing to 0, including single 0s.
* - Negatives: prefix can be negative, map handles it.
* - Duplicate prefixes: frequency counts multiple occurrences.
*
* @param {number[]} nums - the input array of integers
* @param {number} k - the target sum
* @returns {number} the count of subarrays with sum equal to k
*/
function subarraySum(nums, k) {
const prefixMap = new Map(); // Use Map for integer keys, handles negatives
prefixMap.set(0, 1); // Initialize for subarrays starting at 0
let prefixSum = 0; // Current cumulative sum
let count = 0; // Result counter
for (let i = 0; i < nums.length; i++) {
prefixSum += nums[i]; // Update prefix sum
// Check if (prefixSum - k) exists before updating map
if (prefixMap.has(prefixSum - k)) {
count += prefixMap.get(prefixSum - k); // Add frequency of matching prefixes
}
// Update map with current prefixSum
prefixMap.set(prefixSum, (prefixMap.get(prefixSum) || 0) + 1);
}
return count;
}
// Test runner for Node.js environment
if (require.main === module) {
console.log(subarraySum([1,1,1], 2)); // 2
console.log(subarraySum([1,2,3], 3)); // 2
console.log(subarraySum([1,-1,0], 0)); // 2
console.log(subarraySum([], 0)); // 0
console.log(subarraySum([0], 0)); // 1
}
"""
Brute-force approach: Iterate over all possible subarrays and compute their sums.
For each starting index i, accumulate sum from i to j and check if it equals k.
This ensures correctness but is inefficient for large n due to quadratic time.
Why this solution:
- It directly checks every contiguous subarray, guaranteeing we count all valid ones.
- No additional data structures needed, simple to implement and understand.
Where to use:
- Small arrays (n <= 1000) or to demonstrate baseline correctness in interviews.
- When optimizing for space over time.
Complexity:
- Time: O(n^2) - Two nested loops: outer for start, inner for end, summing in O(1) per step with accumulation.
- Space: O(1) - Only a few variables for sum and count.
Interview notes:
- Start with this in interviews to show you understand the problem definition.
- Explain why it's slow: for n=2e4, it does ~2e8 operations, which may timeout.
- Transition to optimized prefix sum approach for better performance.
- Handles negatives/zeros correctly since it recomputes sums each time.
Edge cases handled:
- Empty array: loops don't run, count=0.
- Single element: checked if nums[0] == k.
- All zeros, k=0: counts all non-empty subarrays.
"""
class Solution:
def subarraySum(self, nums: list[int], k: int) -> int:
if not nums:
return 0
count = 0
for i in range(len(nums)):
current_sum = 0
for j in range(i, len(nums)):
current_sum += nums[j]
if current_sum == k:
count += 1
return count
if __name__ == "__main__":
sol = Solution()
print(sol.subarraySum([1,1,1], 2))
print(sol.subarraySum([1,2,3], 3))
print(sol.subarraySum([1,-1,0], 0))
print(sol.subarraySum([], 0))
print(sol.subarraySum([0], 0))
# File: python.brute.py
# Brute-force Subarray Sum Equals K
# O(n^2) time, O(1) extra space (n = len(nums))
"""
Brute-force approach: Iterate over all possible subarrays and compute their sums.
For each starting index i, accumulate sum from i to j and check if it equals k.
This ensures correctness but is inefficient for large n due to quadratic time.
Why this solution:
- It directly checks every contiguous subarray, guaranteeing we count all valid ones.
- No additional data structures needed, simple to implement and understand.
Where to use:
- Small arrays (n <= 1000) or to demonstrate baseline correctness in interviews.
- When optimizing for space over time.
Complexity:
- Time: O(n^2) - Two nested loops: outer for start, inner for end, summing in O(1) per step with accumulation.
- Space: O(1) - Only a few variables for sum and count.
Interview notes:
- Start with this in interviews to show you understand the problem definition.
- Explain why it's slow: for n=2e4, it does ~2e8 operations, which may timeout.
- Transition to optimized prefix sum approach for better performance.
- Handles negatives/zeros correctly since it recomputes sums each time.
Edge cases handled:
- Empty array: loops don't run, count=0.
- Single element: checked if nums[0] == k.
- All zeros, k=0: counts all non-empty subarrays.
"""
class Solution:
def subarraySum(self, nums: list[int], k: int) -> int:
if not nums: # Early return for empty list
return 0
count = 0
for i in range(len(nums)): # Outer loop: start of subarray
current_sum = 0 # Reset sum for each new start
for j in range(i, len(nums)): # Inner loop: end of subarray
current_sum += nums[j] # Accumulate sum incrementally (O(1) per addition)
if current_sum == k: # Check after each addition
count += 1 # Increment if match found
return count
# Test runner
if __name__ == "__main__":
sol = Solution()
print(sol.subarraySum([1,1,1], 2)) # 2
print(sol.subarraySum([1,2,3], 3)) # 2
print(sol.subarraySum([1,-1,0], 0)) # 2
print(sol.subarraySum([], 0)) # 0
print(sol.subarraySum([0], 0)) # 1
"""
Optimized approach: Use prefix sums to represent cumulative sum up to each index.
Maintain a hash map (dict) of prefixSum -> frequency.
For each index, check if (currentPrefix - k) exists in map, adding its frequency to count.
Update map after check to avoid invalid self-counts.
Why this solution:
- Prefix sums allow O(1) subarray sum computation via subtraction.
- Hash map enables O(1) lookups for previous prefixes where difference == k.
- Handles negative numbers and zeros seamlessly, unlike sliding window.
Where to use:
- Large arrays (up to 2e4) as per constraints, efficient in time.
- When counting all subarrays with exact sum is needed.
Complexity:
- Time: O(n) - Single pass through array, each operation (add, check, update) is O(1) amortized.
- Space: O(n) - Dict can store up to n unique prefix sums in worst case.
Interview notes:
- Explain prefix sum concept: sum[i..j] = prefix[j] - prefix[i-1].
- Highlight initializing dict with {0:1} for subarrays starting at index 0.
- Discuss why order matters: check before update to prevent counting current prefix incorrectly.
- Compare to brute: from O(n^2) to O(n), big win for large n.
- In Python, dict handles integer keys safely, including negatives.
Edge cases handled:
- Empty array: loop doesn't run, count=0.
- k=0: correctly counts subarrays summing to 0, including single 0s.
- Negatives: prefix can be negative, dict handles it.
- Duplicate prefixes: frequency counts multiple occurrences.
"""
from typing import List
class Solution:
def subarraySum(self, nums: List[int], k: int) -> int:
prefix_map = {0: 1}
prefix_sum = 0
count = 0
for num in nums:
prefix_sum += num
if prefix_sum - k in prefix_map:
count += prefix_map[prefix_sum - k]
prefix_map[prefix_sum] = prefix_map.get(prefix_sum, 0) + 1
return count
if __name__ == "__main__":
sol = Solution()
print(sol.subarraySum([1,1,1], 2))
print(sol.subarraySum([1,2,3], 3))
print(sol.subarraySum([1,-1,0], 0))
print(sol.subarraySum([], 0))
print(sol.subarraySum([0], 0))
# File: python.optimized.py
# Optimized Subarray Sum Equals K using Prefix Sum and Hash Map
# O(n) time average, O(n) space
"""
Optimized approach: Use prefix sums to represent cumulative sum up to each index.
Maintain a hash map (dict) of prefixSum -> frequency.
For each index, check if (currentPrefix - k) exists in map, adding its frequency to count.
Update map after check to avoid invalid self-counts.
Why this solution:
- Prefix sums allow O(1) subarray sum computation via subtraction.
- Hash map enables O(1) lookups for previous prefixes where difference == k.
- Handles negative numbers and zeros seamlessly, unlike sliding window.
Where to use:
- Large arrays (up to 2e4) as per constraints, efficient in time.
- When counting all subarrays with exact sum is needed.
Complexity:
- Time: O(n) - Single pass through array, each operation (add, check, update) is O(1) amortized.
- Space: O(n) - Dict can store up to n unique prefix sums in worst case.
Interview notes:
- Explain prefix sum concept: sum[i..j] = prefix[j] - prefix[i-1].
- Highlight initializing dict with {0:1} for subarrays starting at index 0.
- Discuss why order matters: check before update to prevent counting current prefix incorrectly.
- Compare to brute: from O(n^2) to O(n), big win for large n.
- In Python, dict handles integer keys safely, including negatives.
Edge cases handled:
- Empty array: loop doesn't run, count=0.
- k=0: correctly counts subarrays summing to 0, including single 0s.
- Negatives: prefix can be negative, dict handles it.
- Duplicate prefixes: frequency counts multiple occurrences.
"""
from typing import List
class Solution:
def subarraySum(self, nums: List[int], k: int) -> int:
prefix_map = {0: 1} # Initialize for subarrays starting at 0
prefix_sum = 0 # Current cumulative sum
count = 0 # Result counter
for num in nums:
prefix_sum += num # Update prefix sum
# Check if (prefix_sum - k) exists before updating map
if prefix_sum - k in prefix_map:
count += prefix_map[prefix_sum - k] # Add frequency of matching prefixes
# Update map with current prefix_sum
prefix_map[prefix_sum] = prefix_map.get(prefix_sum, 0) + 1
return count
# Test runner
if __name__ == "__main__":
sol = Solution()
print(sol.subarraySum([1,1,1], 2)) # 2
print(sol.subarraySum([1,2,3], 3)) # 2
print(sol.subarraySum([1,-1,0], 0)) # 2
print(sol.subarraySum([], 0)) # 0
print(sol.subarraySum([0], 0)) # 1
class Solution {
public int subarraySum(int[] nums, int k) {
if (nums == null || nums.length == 0) return 0;
int count = 0;
for (int i = 0; i < nums.length; i++) {
int currentSum = 0;
for (int j = i; j < nums.length; j++) {
currentSum += nums[j];
if (currentSum == k) {
count++;
}
}
}
return count;
}
public static void main(String[] args) {
Solution sol = new Solution();
System.out.println(sol.subarraySum(new int[]{1,1,1}, 2));
System.out.println(sol.subarraySum(new int[]{1,2,3}, 3));
System.out.println(sol.subarraySum(new int[]{1,-1,0}, 0));
System.out.println(sol.subarraySum(new int[]{}, 0));
System.out.println(sol.subarraySum(new int[]{0}, 0));
}
}
// File: java.brute.java
// Brute-force Subarray Sum Equals K
// O(n^2) time, O(1) extra space (n = nums.length)
/**
* Brute-force approach: Iterate over all possible subarrays and compute their sums.
* For each starting index i, accumulate sum from i to j and check if it equals k.
* This ensures correctness but is inefficient for large n due to quadratic time.
*
* Why this solution:
* - It directly checks every contiguous subarray, guaranteeing we count all valid ones.
* - No additional data structures needed, simple to implement and understand.
*
* Where to use:
* - Small arrays (n <= 1000) or to demonstrate baseline correctness in interviews.
* - When optimizing for space over time.
*
* Complexity:
* - Time: O(n^2) - Two nested loops: outer for start, inner for end, summing in O(1) per step with accumulation.
* - Space: O(1) - Only a few variables for sum and count.
*
* Interview notes:
* - Start with this in interviews to show you understand the problem definition.
* - Explain why it's slow: for n=2e4, it does ~2e8 operations, which may timeout.
* - Transition to optimized prefix sum approach for better performance.
* - Handles negatives/zeros correctly since it recomputes sums each time.
*
* Edge cases handled:
* - Empty array: loops don't run, count=0.
* - Single element: checked if nums[0] == k.
* - All zeros, k=0: counts all non-empty subarrays.
*/
class Solution {
public int subarraySum(int[] nums, int k) {
if (nums == null || nums.length == 0) return 0; // Early return for empty array
int count = 0;
for (int i = 0; i < nums.length; i++) { // Outer loop: start of subarray
int currentSum = 0; // Reset sum for each new start
for (int j = i; j < nums.length; j++) { // Inner loop: end of subarray
currentSum += nums[j]; // Accumulate sum incrementally (O(1) per addition)
if (currentSum == k) { // Check after each addition
count++; // Increment if match found
}
}
}
return count;
}
// Test runner
public static void main(String[] args) {
Solution sol = new Solution();
System.out.println(sol.subarraySum(new int[]{1,1,1}, 2)); // 2
System.out.println(sol.subarraySum(new int[]{1,2,3}, 3)); // 2
System.out.println(sol.subarraySum(new int[]{1,-1,0}, 0)); // 2
System.out.println(sol.subarraySum(new int[]{}, 0)); // 0
System.out.println(sol.subarraySum(new int[]{0}, 0)); // 1
}
}
import java.util.HashMap;
import java.util.Map;
class Solution {
public int subarraySum(int[] nums, int k) {
Map<Integer, Integer> prefixMap = new HashMap<>();
prefixMap.put(0, 1);
int prefixSum = 0;
int count = 0;
for (int num : nums) {
prefixSum += num;
if (prefixMap.containsKey(prefixSum - k)) {
count += prefixMap.get(prefixSum - k);
}
prefixMap.put(prefixSum, prefixMap.getOrDefault(prefixSum, 0) + 1);
}
return count;
}
public static void main(String[] args) {
Solution sol = new Solution();
System.out.println(sol.subarraySum(new int[]{1,1,1}, 2));
System.out.println(sol.subarraySum(new int[]{1,2,3}, 3));
System.out.println(sol.subarraySum(new int[]{1,-1,0}, 0));
System.out.println(sol.subarraySum(new int[]{}, 0));
System.out.println(sol.subarraySum(new int[]{0}, 0));
}
}
// File: java.optimized.java
// Optimized Subarray Sum Equals K using Prefix Sum and Hash Map
// O(n) time average, O(n) space
/**
* Optimized approach: Use prefix sums to represent cumulative sum up to each index.
* Maintain a hash map of prefixSum -> frequency.
* For each index, check if (currentPrefix - k) exists in map, adding its frequency to count.
* Update map after check to avoid invalid self-counts.
*
* Why this solution:
* - Prefix sums allow O(1) subarray sum computation via subtraction.
* - Hash map enables O(1) lookups for previous prefixes where difference == k.
* - Handles negative numbers and zeros seamlessly, unlike sliding window.
*
* Where to use:
* - Large arrays (up to 2e4) as per constraints, efficient in time.
* - When counting all subarrays with exact sum is needed.
*
* Complexity:
* - Time: O(n) - Single pass through array, each operation (add, check, update) is O(1) amortized.
* - Space: O(n) - Hash map can store up to n unique prefix sums in worst case.
*
* Interview notes:
* - Explain prefix sum concept: sum[i..j] = prefix[j] - prefix[i-1].
* - Highlight initializing map with {0:1} for subarrays starting at index 0.
* - Discuss why order matters: check before update to prevent counting current prefix incorrectly.
* - Compare to brute: from O(n^2) to O(n), big win for large n.
* - In Java, use HashMap<Integer, Integer> for integer keys, handles negatives.
*
* Edge cases handled:
* - Empty array: loop doesn't run, count=0.
* - k=0: correctly counts subarrays summing to 0, including single 0s.
* - Negatives: prefix can be negative, map handles it.
* - Duplicate prefixes: frequency counts multiple occurrences.
*/
import java.util.HashMap;
import java.util.Map;
class Solution {
public int subarraySum(int[] nums, int k) {
Map<Integer, Integer> prefixMap = new HashMap<>(); // HashMap for prefixSum -> frequency
prefixMap.put(0, 1); // Initialize for subarrays starting at 0
int prefixSum = 0; // Current cumulative sum
int count = 0; // Result counter
for (int num : nums) {
prefixSum += num; // Update prefix sum
// Check if (prefixSum - k) exists before updating map
if (prefixMap.containsKey(prefixSum - k)) {
count += prefixMap.get(prefixSum - k); // Add frequency of matching prefixes
}
// Update map with current prefixSum
prefixMap.put(prefixSum, prefixMap.getOrDefault(prefixSum, 0) + 1);
}
return count;
}
// Test runner
public static void main(String[] args) {
Solution sol = new Solution();
System.out.println(sol.subarraySum(new int[]{1,1,1}, 2)); // 2
System.out.println(sol.subarraySum(new int[]{1,2,3}, 3)); // 2
System.out.println(sol.subarraySum(new int[]{1,-1,0}, 0)); // 2
System.out.println(sol.subarraySum(new int[]{}, 0)); // 0
System.out.println(sol.subarraySum(new int[]{0}, 0)); // 1
}
}
#include <vector>
using namespace std;
class Solution {
public:
int subarraySum(vector<int>& nums, int k) {
if (nums.empty()) return 0;
int count = 0;
for (int i = 0; i < nums.size(); i++) {
int currentSum = 0;
for (int j = i; j < nums.size(); j++) {
currentSum += nums[j];
if (currentSum == k) {
count++;
}
}
}
return count;
}
};
#include <iostream>
int main() {
Solution sol;
vector<int> test1 = {1, 1, 1};
vector<int> test2 = {1, 2, 3};
vector<int> test3 = {1, -1, 0};
vector<int> test4 = {};
vector<int> test5 = {0};
cout << sol.subarraySum(test1, 2) << endl;
cout << sol.subarraySum(test2, 3) << endl;
cout << sol.subarraySum(test3, 0) << endl;
cout << sol.subarraySum(test4, 0) << endl;
cout << sol.subarraySum(test5, 0) << endl;
return 0;
}
// File: cpp.brute.cpp
// Brute-force Subarray Sum Equals K
// O(n^2) time, O(1) extra space (n = nums.size())
/**
* Brute-force approach: Iterate over all possible subarrays and compute their sums.
* For each starting index i, accumulate sum from i to j and check if it equals k.
* This ensures correctness but is inefficient for large n due to quadratic time.
*
* Why this solution:
* - Directly checks every contiguous subarray, guaranteeing all valid ones are counted.
* - No additional data structures needed, simple to implement and understand.
*
* Where to use:
* - Small arrays (n <= 1000) or to demonstrate baseline correctness in interviews.
* - When optimizing for space over time.
*
* Complexity:
* - Time: O(n^2) - Two nested loops: outer for start, inner for end, summing in O(1) per step with accumulation.
* - Space: O(1) - Only a few variables for sum and count.
*
* Interview notes:
* - Start with this in interviews to show you understand the problem definition.
* - Explain why it's slow: for n=2e4, it does ~2e8 operations, which may timeout.
* - Transition to optimized prefix sum approach for better performance.
* - Handles negatives/zeros correctly since it recomputes sums each time.
*
* Edge cases handled:
* - Empty array: loops don't run, count=0.
* - Single element: checked if nums[0] == k.
* - All zeros, k=0: counts all non-empty subarrays.
*/
#include <vector>
using namespace std;
class Solution {
public:
int subarraySum(vector<int>& nums, int k) {
if (nums.empty()) return 0; // Early return for empty array
int count = 0;
for (int i = 0; i < nums.size(); i++) { // Outer loop: start of subarray
int currentSum = 0; // Reset sum for each new start
for (int j = i; j < nums.size(); j++) { // Inner loop: end of subarray
currentSum += nums[j]; // Accumulate sum incrementally (O(1) per addition)
if (currentSum == k) { // Check after each addition
count++; // Increment if match found
}
}
}
return count;
}
};
// Test runner
#include <iostream>
int main() {
Solution sol;
vector<int> test1 = {1, 1, 1};
vector<int> test2 = {1, 2, 3};
vector<int> test3 = {1, -1, 0};
vector<int> test4 = {};
vector<int> test5 = {0};
cout << sol.subarraySum(test1, 2) << endl; // 2
cout << sol.subarraySum(test2, 3) << endl; // 2
cout << sol.subarraySum(test3, 0) << endl; // 2
cout << sol.subarraySum(test4, 0) << endl; // 0
cout << sol.subarraySum(test5, 0) << endl; // 1
return 0;
}
#include <vector>
#include <unordered_map>
using namespace std;
class Solution {
public:
int subarraySum(vector<int>& nums, int k) {
unordered_map<long long, int> prefixMap;
prefixMap[0] = 1;
long long prefixSum = 0;
int count = 0;
for (int num : nums) {
prefixSum += num;
if (prefixMap.find(prefixSum - k) != prefixMap.end()) {
count += prefixMap[prefixSum - k];
}
prefixMap[prefixSum]++;
}
return count;
}
};
#include <iostream>
int main() {
Solution sol;
vector<int> test1 = {1, 1, 1};
vector<int> test2 = {1, 2, 3};
vector<int> test3 = {1, -1, 0};
vector<int> test4 = {};
vector<int> test5 = {0};
cout << sol.subarraySum(test1, 2) << endl;
cout << sol.subarraySum(test2, 3) << endl;
cout << sol.subarraySum(test3, 0) << endl;
cout << sol.subarraySum(test4, 0) << endl;
cout << sol.subarraySum(test5, 0) << endl;
return 0;
}
// File: cpp.optimized.cpp
// Optimized Subarray Sum Equals K using Prefix Sum and Hash Map
// O(n) time average, O(n) space
/**
* Optimized approach: Use prefix sums to represent cumulative sum up to each index.
* Maintain an unordered_map of prefixSum -> frequency.
* For each index, check if (currentPrefix - k) exists in map, adding its frequency to count.
* Update map after check to avoid invalid self-counts.
*
* Why this solution:
* - Prefix sums allow O(1) subarray sum computation via subtraction.
* - Hash map enables O(1) lookups for previous prefixes where difference == k.
* - Handles negative numbers and zeros seamlessly, unlike sliding window.
*
* Where to use:
* - Large arrays (up to 2e4) as per constraints, efficient in time.
* - When counting all subarrays with exact sum is needed.
*
* Complexity:
* - Time: O(n) - Single pass through array, each operation (add, check, update) is O(1) amortized.
* - Space: O(n) - Hash map can store up to n unique prefix sums in worst case.
*
* Interview notes:
* - Explain prefix sum concept: sum[i..j] = prefix[j] - prefix[i-1].
* - Highlight initializing map with {0:1} for subarrays starting at index 0.
* - Discuss why order matters: check before update to prevent counting current prefix incorrectly.
* - Compare to brute: from O(n^2) to O(n), big win for large n.
* - In C++, use unordered_map for O(1) average-case lookups, handles integer keys.
*
* Edge cases handled:
* - Empty array: loop doesn't run, count=0.
* S k=0: correctly counts subarrays summing to 0, including single 0s.
* - Negatives: prefix can be negative, map handles it.
* - Duplicate prefixes: frequency counts multiple occurrences.
*/
#include <vector>
#include <unordered_map>
using namespace std;
class Solution {
public:
int subarraySum(vector<int>& nums, int k) {
unordered_map<long long, int> prefixMap; // Use long long for large sums
prefixMap[0] = 1; // Initialize for subarrays starting at 0
long long prefixSum = 0; // Current cumulative sum
int count = 0; // Result counter
for (int num : nums) {
prefixSum += num; // Update prefix sum
// Check if (prefixSum - k) exists before updating map
if (prefixMap.find(prefixSum - k) != prefixMap.end()) {
count += prefixMap[prefixSum - k]; // Add frequency of matching prefixes
}
// Update map with current prefixSum
prefixMap[prefixSum]++;
}
return count;
}
};
// Test runner
#include <iostream>
int main() {
Solution sol;
vector<int> test1 = {1, 1, 1};
vector<int> test2 = {1, 2, 3};
vector<int> test3 = {1, -1, 0};
vector<int> test4 = {};
vector<int> test5 = {0};
cout << sol.subarraySum(test1, 2) << endl; // 2
cout << sol.subarraySum(test2, 3) << endl; // 2
cout << sol.subarraySum(test3, 0) << endl; // 2
cout << sol.subarraySum(test4, 0) << endl; // 0
cout << sol.subarraySum(test5, 0) << endl; // 1
return 0;
}
public class Solution {
public int SubarraySum(int[] nums, int k) {
if (nums == null || nums.Length == 0) return 0;
int count = 0;
for (int i = 0; i < nums.Length; i++) {
int currentSum = 0;
for (int j = i; j < nums.Length; j++) {
currentSum += nums[j];
if (currentSum == k) {
count++;
}
}
}
return count;
}
}
using System;
class Program {
static void Main() {
Solution sol = new Solution();
Console.WriteLine(sol.SubarraySum(new int[] {1, 1, 1}, 2));
Console.WriteLine(sol.SubarraySum(new int[] {1, 2, 3}, 3));
Console.WriteLine(sol.SubarraySum(new int[] {1, -1, 0}, 0));
Console.WriteLine(sol.SubarraySum(new int[] {}, 0));
Console.WriteLine(sol.SubarraySum(new int[] {0}, 0));
}
}
// File: csharp.brute.cs
// Brute-force Subarray Sum Equals K
// O(n^2) time, O(1) extra space (n = nums.Length)
/**
* Brute-force approach: Iterate over all possible subarrays and compute their sums.
* For each starting index i, accumulate sum from i to j and check if it equals k.
* This ensures correctness but is inefficient for large n due to quadratic time.
*
* Why this solution:
* - Directly checks every contiguous subarray, guaranteeing all valid ones are counted.
* - No additional data structures needed, simple to implement and understand.
*
* Where to use:
* - Small arrays (n <= 1000) or to demonstrate baseline correctness in interviews.
* - When optimizing for space over time.
*
* Complexity:
* - Time: O(n^2) - Two nested loops: outer for start, inner for end, summing in O(1) per step with accumulation.
* - Space: O(1) - Only a few variables for sum and count.
*
* Interview notes:
* - Start with this in interviews to show you understand the problem definition.
* - Explain why it's slow: for n=2e4, it does ~2e8 operations, which may timeout.
* - Transition to optimized prefix sum approach for better performance.
* - Handles negatives/zeros correctly since it recomputes sums each time.
*
* Edge cases handled:
* - Empty array: loops don't run, count=0.
* - Single element: checked if nums[0] == k.
* - All zeros, k=0: counts all non-empty subarrays.
*/
public class Solution {
public int SubarraySum(int[] nums, int k) {
if (nums == null || nums.Length == 0) return 0; // Early return for empty array
int count = 0;
for (int i = 0; i < nums.Length; i++) { // Outer loop: start of subarray
int currentSum = 0; // Reset sum for each new start
for (int j = i; j < nums.Length; j++) { // Inner loop: end of subarray
currentSum += nums[j]; // Accumulate sum incrementally (O(1) per addition)
if (currentSum == k) { // Check after each addition
count++; // Increment if match found
}
}
}
return count;
}
}
// Test runner
using System;
class Program {
static void Main() {
Solution sol = new Solution();
Console.WriteLine(sol.SubarraySum(new int[] {1, 1, 1}, 2)); // 2
Console.WriteLine(sol.SubarraySum(new int[] {1, 2, 3}, 3)); // 2
Console.WriteLine(sol.SubarraySum(new int[] {1, -1, 0}, 0)); // 2
Console.WriteLine(sol.SubarraySum(new int[] {}, 0)); // 0
Console.WriteLine(sol.SubarraySum(new int[] {0}, 0)); // 1
}
}
using System;
using System.Collections.Generic;
public class Solution {
public int SubarraySum(int[] nums, int k) {
Dictionary<long, int> prefixMap = new Dictionary<long, int>();
prefixMap[0] = 1;
long prefixSum = 0;
int count = 0;
foreach (int num in nums) {
prefixSum += num;
if (prefixMap.ContainsKey(prefixSum - k)) {
count += prefixMap[prefixSum - k];
}
prefixMap[prefixSum] = prefixMap.GetValueOrDefault(prefixSum, 0) + 1;
}
return count;
}
}
class Program {
static void Main() {
Solution sol = new Solution();
Console.WriteLine(sol.SubarraySum(new int[] {1, 1, 1}, 2));
Console.WriteLine(sol.SubarraySum(new int[] {1, 2, 3}, 3));
Console.WriteLine(sol.SubarraySum(new int[] {1, -1, 0}, 0));
Console.WriteLine(sol.SubarraySum(new int[] {}, 0));
Console.WriteLine(sol.SubarraySum(new int[] {0}, 0));
}
}
// File: csharp.optimized.cs
// Optimized Subarray Sum Equals K using Prefix Sum and Hash Map
// O(n) time average, O(n) space
/**
* Optimized approach: Use prefix sums to represent cumulative sum up to each index.
* Maintain a dictionary of prefixSum -> frequency.
* For each index, check if (currentPrefix - k) exists in map, adding its frequency to count.
* Update map after check to avoid invalid self-counts.
*
* Why this solution:
* - Prefix sums allow O(1) subarray sum computation via subtraction.
* - Hash map enables O(1) lookups for previous prefixes where difference == k.
* - Handles negative numbers and zeros seamlessly, unlike sliding window.
*
* Where to use:
* - Large arrays (up to 2e4) as per constraints, efficient in time.
* - When counting all subarrays with exact sum is needed.
*
* Complexity:
* - Time: O(n) - Single pass through array, each operation (add, check, update) is O(1) amortized.
* - Space: O(n) - Dictionary can store up to n unique prefix sums in worst case.
*
* Interview notes:
* - Explain prefix sum concept: sum[i..j] = prefix[j] - prefix[i-1].
* - Highlight initializing dictionary with {0:1} for subarrays starting at index 0.
* - Discuss why order matters: check before update to prevent counting current prefix incorrectly.
* - Compare to brute: from O(n^2) to O(n), big win for large n.
* - In C#, use Dictionary<long, int> for integer keys, handles large/negative sums.
*
* Edge cases handled:
* - Empty array: loop doesn't run, count=0.
* - k=0: correctly counts subarrays summing to 0, including single 0s.
* - Negatives: prefix can be negative, dictionary handles it.
* - Duplicate prefixes: frequency counts multiple occurrences.
*/
using System;
using System.Collections.Generic;
public class Solution {
public int SubarraySum(int[] nums, int k) {
Dictionary<long, int> prefixMap = new Dictionary<long, int>(); // Use long for large sums
prefixMap[0] = 1; // Initialize for subarrays starting at 0
long prefixSum = 0; // Current cumulative sum
int count = 0; // Result counter
foreach (int num in nums) {
prefixSum += num; // Update prefix sum
// Check if (prefixSum - k) exists before updating map
if (prefixMap.ContainsKey(prefixSum - k)) {
count += prefixMap[prefixSum - k]; // Add frequency of matching prefixes
}
// Update map with current prefixSum
prefixMap[prefixSum] = prefixMap.GetValueOrDefault(prefixSum, 0) + 1;
}
return count;
}
}
// Test runner
class Program {
static void Main() {
Solution sol = new Solution();
Console.WriteLine(sol.SubarraySum(new int[] {1, 1, 1}, 2)); // 2
Console.WriteLine(sol.SubarraySum(new int[] {1, 2, 3}, 3)); // 2
Console.WriteLine(sol.SubarraySum(new int[] {1, -1, 0}, 0)); // 2
Console.WriteLine(sol.SubarraySum(new int[] {}, 0)); // 0
Console.WriteLine(sol.SubarraySum(new int[] {0}, 0)); // 1
}
}
package main
import "fmt"
func subarraySum(nums []int, k int) int {
if len(nums) == 0 {
return 0
}
count := 0
for i := 0; i < len(nums); i++ {
currentSum := 0
for j := i; j < len(nums); j++ {
currentSum += nums[j]
if currentSum == k {
count++
}
}
}
return count
}
func main() {
fmt.Println(subarraySum([]int{1, 1, 1}, 2))
fmt.Println(subarraySum([]int{1, 2, 3}, 3))
fmt.Println(subarraySum([]int{1, -1, 0}, 0))
fmt.Println(subarraySum([]int{}, 0))
fmt.Println(subarraySum([]int{0}, 0))
}
// File: go.brute.go
// Brute-force Subarray Sum Equals K
// O(n^2) time, O(1) extra space (n = len(nums))
/*
Brute-force approach: Iterate over all possible subarrays and compute their sums.
For each starting index i, accumulate sum from i to j and check if it equals k.
This ensures correctness but is inefficient for large n due to quadratic time.
Why this solution:
- Directly checks every contiguous subarray, guaranteeing all valid ones are counted.
- No additional data structures needed, simple to implement and understand.
Where to use:
- Small arrays (n <= 1000) or to demonstrate baseline correctness in interviews.
- When optimizing for space over time.
Complexity:
- Time: O(n^2) - Two nested loops: outer for start, inner for end, summing in O(1) per step with accumulation.
- Space: O(1) - Only a few variables for sum and count.
Interview notes:
- Start with this in interviews to show you understand the problem definition.
- Explain why it's slow: for n=2e4, it does ~2e8 operations, which may timeout.
- Transition to optimized prefix sum approach for better performance.
- Handles negatives/zeros correctly since it recomputes sums each time.
Edge cases handled:
- Empty array: loops don't run, count=0.
- Single element: checked if nums[0] == k.
- All zeros, k=0: counts all non-empty subarrays.
*/
package main
import "fmt"
func subarraySum(nums []int, k int) int {
if len(nums) == 0 { // Early return for empty array
return 0
}
count := 0
for i := 0; i < len(nums); i++ { // Outer loop: start of subarray
currentSum := 0 // Reset sum for each new start
for j := i; j < len(nums); j++ { // Inner loop: end of subarray
currentSum += nums[j] // Accumulate sum incrementally (O(1) per addition)
if currentSum == k { // Check after each addition
count++ // Increment if match found
}
}
}
return count
}
// Test runner
func main() {
fmt.Println(subarraySum([]int{1, 1, 1}, 2)) // 2
fmt.Println(subarraySum([]int{1, 2, 3}, 3)) // 2
fmt.Println(subarraySum([]int{1, -1, 0}, 0)) // 2
fmt.Println(subarraySum([]int{}, 0)) // 0
fmt.Println(subarraySum([]int{0}, 0)) // 1
}
package main
import "fmt"
func subarraySum(nums []int, k int) int {
prefixMap := make(map[int64]int)
prefixMap[0] = 1
var prefixSum int64 = 0
count := 0
for _, num := range nums {
prefixSum += int64(num)
if freq, exists := prefixMap[prefixSum-int64(k)]; exists {
count += freq
}
prefixMap[prefixSum]++
}
return count
}
func main() {
fmt.Println(subarraySum([]int{1, 1, 1}, 2))
fmt.Println(subarraySum([]int{1, 2, 3}, 3))
fmt.Println(subarraySum([]int{1, -1, 0}, 0))
fmt.Println(subarraySum([]int{}, 0))
fmt.Println(subarraySum([]int{0}, 0))
}
// File: go.optimized.go
// Optimized Subarray Sum Equals K using Prefix Sum and Hash Map
// O(n) time average, O(n) space
/*
Optimized approach: Use prefix sums to represent cumulative sum up to each index.
Maintain a map of prefixSum -> frequency.
For each index, check if (currentPrefix - k) exists in map, adding its frequency to count.
Update map after check to avoid invalid self-counts.
Why this solution:
- Prefix sums allow O(1) subarray sum computation via subtraction.
- Hash map enables O(1) lookups for previous prefixes where difference == k.
- Handles negative numbers and zeros seamlessly, unlike sliding window.
Where to use:
- Large arrays (up to 2e4) as per constraints, efficient in time.
- When counting all subarrays with exact sum is needed.
Complexity:
- Time: O(n) - Single pass through array, each operation (add, check, update) is O(1) amortized.
- Space: O(n) - Map can store up to n unique prefix sums in worst case.
Interview notes:
- Explain prefix sum concept: sum[i..j] = prefix[j] - prefix[i-1].
- Highlight initializing map with {0:1} for subarrays starting at index 0.
- Discuss why order matters: check before update to prevent counting current prefix incorrectly.
- Compare to brute: from O(n^2) to O(n), big win for large n.
- In Go, use map[int64]int for integer keys to handle large/negative sums.
Edge cases handled:
- Empty array: loop doesn't run, count=0.
- k=0: correctly counts subarrays summing to 0, including single 0s.
- Negatives: prefix can be negative, map handles it.
- Duplicate prefixes: frequency counts multiple occurrences.
*/
package main
import "fmt"
func subarraySum(nums []int, k int) int {
prefixMap := make(map[int64]int) // Use int64 for large sums
prefixMap[0] = 1 // Initialize for subarrays starting at 0
var prefixSum int64 = 0 // Current cumulative sum
count := 0 // Result counter
for _, num := range nums {
prefixSum += int64(num) // Update prefix sum
// Check if (prefixSum - k) exists before updating map
if freq, exists := prefixMap[prefixSum-int64(k)]; exists {
count += freq // Add frequency of matching prefixes
}
// Update map with current prefixSum
prefixMap[prefixSum]++
}
return count
}
// Test runner
func main() {
fmt.Println(subarraySum([]int{1, 1, 1}, 2)) // 2
fmt.Println(subarraySum([]int{1, 2, 3}, 3)) // 2
fmt.Println(subarraySum([]int{1, -1, 0}, 0)) // 2
fmt.Println(subarraySum([]int{}, 0)) // 0
fmt.Println(subarraySum([]int{0}, 0)) // 1
}
class Solution {
subarraySum(nums: number[], k: number): number {
if (!nums || nums.length === 0) return 0;
let count: number = 0;
for (let i: number = 0; i < nums.length; i++) {
let currentSum: number = 0;
for (let j: number = i; j < nums.length; j++) {
currentSum += nums[j];
if (currentSum === k) {
count++;
}
}
}
return count;
}
}
const sol = new Solution();
console.log(sol.subarraySum([1, 1, 1], 2));
console.log(sol.subarraySum([1, 2, 3], 3));
console.log(sol.subarraySum([1, -1, 0], 0));
console.log(sol.subarraySum([], 0));
console.log(sol.subarraySum([0], 0));
// File: typescript.brute.ts
// Brute-force Subarray Sum Equals K
// O(n^2) time, O(1) extra space (n = nums.length)
/**
* Brute-force approach: Iterate over all possible subarrays and compute their sums.
* For each starting index i, accumulate sum from i to j and check if it equals k.
* This ensures correctness but is inefficient for large n due to quadratic time.
*
* Why this solution:
* - Directly checks every contiguous subarray, guaranteeing all valid ones are counted.
* - No additional data structures needed, simple to implement and understand.
*
* Where to use:
* - Small arrays (n <= 1000) or to demonstrate baseline correctness in interviews.
* - When optimizing for space over time.
*
* Complexity:
* - Time: O(n^2) - Two nested loops: outer for start, inner for end, summing in O(1) per step with accumulation.
* - Space: O(1) - Only a few variables for sum and count.
*
* Interview notes:
* - Start with this in interviews to show you understand the problem definition.
* - Explain why it's slow: for n=2e4, it does ~2e8 operations, which may timeout.
* - Transition to optimized prefix sum approach for better performance.
* - Handles negatives/zeros correctly since it recomputes sums each time.
*
* Edge cases handled:
* - Empty array: loops don't run, count=0.
* - Single element: checked if nums[0] === k.
* - All zeros, k=0: counts all non-empty subarrays.
*/
class Solution {
subarraySum(nums: number[], k: number): number {
if (!nums || nums.length === 0) return 0; // Early return for empty array
let count: number = 0;
for (let i: number = 0; i < nums.length; i++) { // Outer loop: start of subarray
let currentSum: number = 0; // Reset sum for each new start
for (let j: number = i; j < nums.length; j++) { // Inner loop: end of subarray
currentSum += nums[j]; // Accumulate sum incrementally (O(1) per addition)
if (currentSum === k) { // Check after each addition
count++; // Increment if match found
}
}
}
return count;
}
}
// Test runner
const sol = new Solution();
console.log(sol.subarraySum([1, 1, 1], 2)); // 2
console.log(sol.subarraySum([1, 2, 3], 3)); // 2
console.log(sol.subarraySum([1, -1, 0], 0)); // 2
console.log(sol.subarraySum([], 0)); // 0
console.log(sol.subarraySum([0], 0)); // 1
class SolutionOptimized {
subarraySum(nums: number[], k: number): number {
const prefixMap: Map<number, number> = new Map();
prefixMap.set(0, 1);
let prefixSum: number = 0;
let count: number = 0;
for (const num of nums) {
prefixSum += num;
if (prefixMap.has(prefixSum - k)) {
count += prefixMap.get(prefixSum - k)!;
}
prefixMap.set(prefixSum, (prefixMap.get(prefixSum) || 0) + 1);
}
return count;
}
}
const solOpt = new Solution();
console.log(sol.subarraySum([1, 1, 1], 2));
console.log(sol.subarraySum([1, 2, 3], 3));
console.log(sol.subarraySum([1, -1, 0], 0));
console.log(sol.subarraySum([], 0));
console.log(sol.subarraySum([0], 0));
// File: typescript.optimized.ts
// Optimized Subarray Sum Equals K using Prefix Sum and Hash Map
// O(n) time average, O(n) space
/**
* Optimized approach: Use prefix sums to represent cumulative sum up to each index.
* Maintain a Map of prefixSum -> frequency.
* For each index, check if (currentPrefix - k) exists in map, adding its frequency to count.
* Update map after check to avoid invalid self-counts.
*
* Why this solution:
* - Prefix sums allow O(1) subarray sum computation via subtraction.
* - Hash map enables O(1) lookups for previous prefixes where difference == k.
* - Handles negative numbers and zeros seamlessly, unlike sliding window.
*
* Where to use:
* - Large arrays (up to 2e4) as per constraints, efficient in time.
* - When counting all subarrays with exact sum is needed.
*
* Complexity:
* - Time: O(n) - Single pass through array, each operation (add, check, update) is O(1) amortized.
* - Space: O(n) - Map can store up to n unique prefix sums in worst case.
*
* Interview notes:
* - Explain prefix sum concept: sum[i..j] = prefix[j] - prefix[i-1].
* - Highlight initializing map with {0:1} for subarrays starting at index 0.
* - Discuss why order matters: check before update to prevent counting current prefix incorrectly.
* - Compare to brute: from O(n^2) to O(n), big win for large n.
* - In TypeScript, use Map<number, number> for type-safe integer keys, handles negatives.
*
* Edge cases handled:
* - Empty array: loop doesn't run, count=0.
* - k=0: correctly counts subarrays summing to 0, including single 0s.
* - Negatives: prefix can be negative, map handles it.
* - Duplicate prefixes: frequency counts multiple occurrences.
*/
class SolutionOptimized {
subarraySum(nums: number[], k: number): number {
const prefixMap: Map<number, number> = new Map(); // Map for prefixSum -> frequency
prefixMap.set(0, 1); // Initialize for subarrays starting at 0
let prefixSum: number = 0; // Current cumulative sum
let count: number = 0; // Result counter
for (const num of nums) {
prefixSum += num; // Update prefix sum
// Check if (prefixSum - k) exists before updating map
if (prefixMap.has(prefixSum - k)) {
count += prefixMap.get(prefixSum - k)!; // Add frequency of matching prefixes
}
// Update map with current prefixSum
prefixMap.set(prefixSum, (prefixMap.get(prefixSum) || 0) + 1);
}
return count;
}
}
// Test runner
const solOpt = new Solution();
console.log(sol.subarraySum([1, 1, 1], 2)); // 2
console.log(sol.subarraySum([1, 2, 3], 3)); // 2
console.log(sol.subarraySum([1, -1, 0], 0)); // 2
console.log(sol.subarraySum([], 0)); // 0
console.log(sol.subarraySum([0], 0)); // 1
def subarray_sum(nums, k)
return 0 if nums.empty?
count = 0
nums.each_index do |i|
current_sum = 0
(i...nums.length).each do |j|
current_sum += nums[j]
count += 1 if current_sum == k
end
end
count
end
if __FILE__ == $PROGRAM_NAME
puts subarray_sum([1, 1, 1], 2)
puts subarray_sum([1, 2, 3], 3)
puts subarray_sum([1, -1, 0], 0)
puts subarray_sum([], 0)
puts subarray_sum([0], 0)
end
# File: ruby.brute.rb
# Brute-force Subarray Sum Equals K
# O(n^2) time, O(1) extra space (n = nums.length)
=begin
Brute-force approach: Iterate over all possible subarrays and compute their sums.
For each starting index i, accumulate sum from i to j and check if it equals k.
This ensures correctness but is inefficient for large n due to quadratic time.
Why this solution:
- Directly checks every contiguous subarray, guaranteeing all valid ones are counted.
- No additional data structures needed, simple to implement and understand.
Where to use:
- Small arrays (n <= 1000) or to demonstrate baseline correctness in interviews.
- When optimizing for space over time.
Complexity:
- Time: O(n^2) - Two nested loops: outer for start, inner for end, summing in O(1) per step with accumulation.
- Space: O(1) - Only a few variables for sum and count.
Interview notes:
- Start with this in interviews to show you understand the problem definition.
- Explain why it's slow: for n=2e4, it does ~2e8 operations, which may timeout.
- Transition to optimized prefix sum approach for better performance.
- Handles negatives/zeros correctly since it recomputes sums each time.
Edge cases handled:
- Empty array: loops don't run, count=0.
- Single element: checked if nums[0] == k.
- All zeros, k=0: counts all non-empty subarrays.
=end
def subarray_sum(nums, k)
return 0 if nums.empty? # Early return for empty array
count = 0
nums.each_index do |i| # Outer loop: start of subarray
current_sum = 0 # Reset sum for each new start
(i...nums.length).each do |j| # Inner loop: end of subarray
current_sum += nums[j] # Accumulate sum incrementally (O(1) per addition)
count += 1 if current_sum == k # Increment if match found
end
end
count
end
# Test runner
if __FILE__ == $PROGRAM_NAME
puts subarray_sum([1, 1, 1], 2) # 2
puts subarray_sum([1, 2, 3], 3) # 2
puts subarray_sum([1, -1, 0], 0) # 2
puts subarray_sum([], 0) # 0
puts subarray_sum([0], 0) # 1
end
def subarray_sum(nums, k)
prefix_map = {0 => 1}
prefix_sum = 0
count = 0
nums.each do |num|
prefix_sum += num
count += prefix_map[prefix_sum - k] if prefix_map.key?(prefix_sum - k)
prefix_map[prefix_sum] = prefix_map.fetch(prefix_sum, 0) + 1
end
count
end
if __FILE__ == $PROGRAM_NAME
puts subarray_sum([1, 1, 1], 2)
puts subarray_sum([1, 2, 3], 3)
puts subarray_sum([1, -1, 0], 0)
puts subarray_sum([], 0)
puts subarray_sum([0], 0)
end
# File: ruby.optimized.rb
# Optimized Subarray Sum Equals K using Prefix Sum and Hash Map
# O(n) time average, O(n) space
=begin
Optimized approach: Use prefix sums to represent cumulative sum up to each index.
Maintain a hash of prefixSum => frequency.
For each index, check if (currentPrefix - k) exists in hash, adding its frequency to count.
Update hash after check to avoid invalid self-counts.
Why this solution:
- Prefix sums allow O(1) subarray sum computation via subtraction.
- Hash map enables O(1) lookups for previous prefixes where difference == k.
- Handles negative numbers and zeros seamlessly, unlike sliding window.
Where to use:
- Large arrays (up to 2e4) as per constraints, efficient in time.
- When counting all subarrays with exact sum is needed.
Complexity:
- Time: O(n) - Single pass through array, each operation (add, check, update) is O(1) amortized.
- Space: O(n) - Hash can store up to n unique prefix sums in worst case.
Interview notes:
- Explain prefix sum concept: sum[i..j] = prefix[j] - prefix[i-1].
- Highlight initializing hash with {0=>1} for subarrays starting at index 0.
- Discuss why order matters: check before update to prevent counting current prefix incorrectly.
- Compare to brute: from O(n^2) to O(n), big win for large n.
- In Ruby, hash handles integer keys, including negatives, safely.
Edge cases handled:
- Empty array: loop doesn't run, count=0.
- k=0: correctly counts subarrays summing to 0, including single 0s.
- Negatives: prefix can be negative, hash handles it.
- Duplicate prefixes: frequency counts multiple occurrences.
=end
def subarray_sum(nums, k)
prefix_map = {0 => 1} # Initialize for subarrays starting at 0
prefix_sum = 0 # Current cumulative sum
count = 0 # Result counter
nums.each do |num|
prefix_sum += num # Update prefix sum
# Check if (prefix_sum - k) exists before updating map
count += prefix_map[prefix_sum - k] if prefix_map.key?(prefix_sum - k)
# Update map with current prefix_sum
prefix_map[prefix_sum] = prefix_map.fetch(prefix_sum, 0) + 1
end
count
end
# Test runner
if __FILE__ == $PROGRAM_NAME
puts subarray_sum([1, 1, 1], 2) # 2
puts subarray_sum([1, 2, 3], 3) # 2
puts subarray_sum([1, -1, 0], 0) # 2
puts subarray_sum([], 0) # 0
puts subarray_sum([0], 0) # 1
end
class Solution {
func subarraySum(_ nums: [Int], _ k: Int) -> Int {
guard !nums.isEmpty else { return 0 }
var count = 0
for i in 0..<nums.count {
var currentSum = 0
for j in i..<nums.count {
currentSum += nums[j]
if currentSum == k {
count += 1
}
}
}
return count
}
}
let sol = Solution()
print(sol.subarraySum([1, 1, 1], 2))
print(sol.subarraySum([1, 2, 3], 3))
print(sol.subarraySum([1, -1, 0], 0))
print(sol.subarraySum([], 0))
print(sol.subarraySum([0], 0))
// File: swift.brute.swift
// Brute-force Subarray Sum Equals K
// O(n^2) time, O(1) extra space (n = nums.count)
/**
* Brute-force approach: Iterate over all possible subarrays and compute their sums.
* For each starting index i, accumulate sum from i to j and check if it equals k.
* This ensures correctness but is inefficient for large n due to quadratic time.
*
* Why this solution:
* - Directly checks every contiguous subarray, guaranteeing all valid ones are counted.
* - No additional data structures needed, simple to implement and understand.
*
* Where to use:
* - Small arrays (n <= 1000) or to demonstrate baseline correctness in interviews.
* - When optimizing for space over time.
*
* Complexity:
* - Time: O(n^2) - Two nested loops: outer for start, inner for end, summing in O(1) per step with accumulation.
* - Space: O(1) - Only a few variables for sum and count.
*
* Interview notes:
* - Start with this in interviews to show you understand the problem definition.
* - Explain why it's slow: for n=2e4, it does ~2e8 operations, which may timeout.
* - Transition to optimized prefix sum approach for better performance.
* - Handles negatives/zeros correctly since it recomputes sums each time.
*
* Edge cases handled:
* - Empty array: loops don't run, count=0.
* - Single element: checked if nums[0] == k.
* - All zeros, k=0: counts all non-empty subarrays.
*/
class Solution {
func subarraySum(_ nums: [Int], _ k: Int) -> Int {
guard !nums.isEmpty else { return 0 } // Early return for empty array
var count = 0
for i in 0..<nums.count { // Outer loop: start of subarray
var currentSum = 0 // Reset sum for each new start
for j in i..<nums.count { // Inner loop: end of subarray
currentSum += nums[j] // Accumulate sum incrementally (O(1) per addition)
if currentSum == k { // Check after each addition
count += 1 // Increment if match found
}
}
}
return count
}
}
// Test runner
let sol = Solution()
print(sol.subarraySum([1, 1, 1], 2)) // 2
print(sol.subarraySum([1, 2, 3], 3)) // 2
print(sol.subarraySum([1, -1, 0], 0)) // 2
print(sol.subarraySum([], 0)) // 0
print(sol.subarraySum([0], 0)) // 1
class Solution {
func subarraySum(_ nums: [Int], _ k: Int) -> Int {
var prefixMap: [Int: Int] = [0: 1]
var prefixSum: Int = 0
var count: Int = 0
for num in nums {
prefixSum += num
if let freq = prefixMap[prefixSum - k] {
count += freq
}
prefixMap[prefixSum, default: 0] += 1
}
return count
}
}
let sol = Solution()
print(sol.subarraySum([1, 1, 1], 2))
print(sol.subarraySum([1, 2, 3], 3))
print(sol.subarraySum([1, -1, 0], 0))
print(sol.subarraySum([], 0))
print(sol.subarraySum([0], 0))
// File: swift.optimized.swift
// Optimized Subarray Sum Equals K using Prefix Sum and Hash Map
// O(n) time average, O(n) space
/**
* Optimized approach: Use prefix sums to represent cumulative sum up to each index.
* Maintain a dictionary of prefixSum -> frequency.
* For each index, check if (currentPrefix - k) exists in map, adding its frequency to count.
* Update map after check to avoid invalid self-counts.
*
* Why this solution:
* - Prefix sums allow O(1) subarray sum computation via subtraction.
* - Hash map enables O(1) lookups for previous prefixes where difference == k.
* - Handles negative numbers and zeros seamlessly, unlike sliding window.
*
* Where to use:
* - Large arrays (up to 2e4) as per constraints, efficient in time.
* - When counting all subarrays with exact sum is needed.
*
* Complexity:
* - Time: O(n) - Single pass through array, each operation (add, check, update) is O(1) amortized.
* - Space: O(n) - Dictionary can store up to n unique prefix sums in worst case.
*
* Interview notes:
* - Explain prefix sum concept: sum[i..j] = prefix[j] - prefix[i-1].
* - Highlight initializing dictionary with {0:1} for subarrays starting at index 0.
* - Discuss why order matters: check before update to prevent counting current prefix incorrectly.
* - Compare to brute: from O(n^2) to O(n), big win for large n.
* - In Swift, use [Int: Int] for integer keys, handles negatives safely.
*
* Edge cases handled:
* - Empty array: loop doesn't run, count=0.
* - k=0: correctly counts subarrays summing to 0, including single 0s.
* - Negatives: prefix can be negative, dictionary handles it.
* - Duplicate prefixes: frequency counts multiple occurrences.
*/
class Solution {
func subarraySum(_ nums: [Int], _ k: Int) -> Int {
var prefixMap: [Int: Int] = [0: 1] // Initialize for subarrays starting at 0
var prefixSum: Int = 0 // Current cumulative sum
var count: Int = 0 // Result counter
for num in nums {
prefixSum += num // Update prefix sum
// Check if (prefixSum - k) exists before updating map
if let freq = prefixMap[prefixSum - k] {
count += freq // Add frequency of matching prefixes
}
// Update map with current prefixSum
prefixMap[prefixSum, default: 0] += 1
}
return count
}
}
// Test runner
let sol = Solution()
print(sol.subarraySum([1, 1, 1], 2)) // 2
print(sol.subarraySum([1, 2, 3], 3)) // 2
print(sol.subarraySum([1, -1, 0], 0)) // 2
print(sol.subarraySum([], 0)) // 0
print(sol.subarraySum([0], 0)) // 1
class Solution {
fun subarraySum(nums: IntArray, k: Int): Int {
if (nums.isEmpty()) return 0
var count = 0
for (i in nums.indices) {
var currentSum = 0
for (j in i until nums.size) {
currentSum += nums[j]
if (currentSum == k) {
count++
}
}
}
return count
}
}
fun main() {
val sol = Solution()
println(sol.subarraySum(intArrayOf(1,1,1), 2))
println(sol.subarraySum(intArrayOf(1,2,3), 3))
println(sol.subarraySum(intArrayOf(1,-1,0), 0))
println(sol.subarraySum(intArrayOf(), 0))
println(sol.subarraySum(intArrayOf(0), 0))
}
// File: kotlin.brute.kt
// Brute-force Subarray Sum Equals K
// O(n^2) time, O(1) extra space (n = nums.size)
/**
* Brute-force approach: Iterate over all possible subarrays and compute their sums.
* For each starting index i, accumulate sum from i to j and check if it equals k.
* This ensures correctness but is inefficient for large n due to quadratic time.
*
* Why this solution:
* - It directly checks every contiguous subarray, guaranteeing we count all valid ones.
* - No additional data structures needed, simple to implement and understand.
*
* Where to use:
* - Small arrays (n <= 1000) or to demonstrate baseline correctness in interviews.
* - When optimizing for space over time.
*
* Complexity:
* - Time: O(n^2) - Two nested loops: outer for start, inner for end, summing in O(1) per step with accumulation.
* - Space: O(1) - Only a few variables for sum and count.
*
* Interview notes:
* - Start with this in interviews to show you understand the problem definition.
* - Explain why it's slow: for n=2e4, it does ~2e8 operations, which may timeout.
* - Transition to optimized prefix sum approach for better performance.
* - Handles negatives/zeros correctly since it recomputes sums each time.
*
* Edge cases handled:
* - Empty array: loops don't run, count=0.
* - Single element: checked if nums[0] == k.
* - All zeros, k=0: counts all non-empty subarrays.
*/
class Solution {
fun subarraySum(nums: IntArray, k: Int): Int {
if (nums.isEmpty()) return 0 // Early return for empty array
var count = 0
for (i in nums.indices) { // Outer loop: start of subarray
var currentSum = 0 // Reset sum for each new start
for (j in i until nums.size) { // Inner loop: end of subarray
currentSum += nums[j] // Accumulate sum incrementally (O(1) per addition)
if (currentSum == k) { // Check after each addition
count++ // Increment if match found
}
}
}
return count
}
}
fun main() {
val sol = Solution()
println(sol.subarraySum(intArrayOf(1,1,1), 2)) // 2
println(sol.subarraySum(intArrayOf(1,2,3), 3)) // 2
println(sol.subarraySum(intArrayOf(1,-1,0), 0)) // 2
println(sol.subarraySum(intArrayOf(), 0)) // 0
println(sol.subarraySum(intArrayOf(0), 0)) // 1
}
class Solution {
fun subarraySum(nums: IntArray, k: Int): Int {
val prefixMap = mutableMapOf<Int, Int>()
prefixMap[0] = 1
var prefixSum = 0
var count = 0
for (num in nums) {
prefixSum += num
if (prefixMap.containsKey(prefixSum - k)) {
count += prefixMap[prefixSum - k]!!
}
prefixMap[prefixSum] = prefixMap.getOrDefault(prefixSum, 0) + 1
}
return count
}
}
fun main() {
val sol = Solution()
println(sol.subarraySum(intArrayOf(1,1,1), 2))
println(sol.subarraySum(intArrayOf(1,2,3), 3))
println(sol.subarraySum(intArrayOf(1,-1,0), 0))
println(sol.subarraySum(intArrayOf(), 0))
println(sol.subarraySum(intArrayOf(0), 0))
}
// File: kotlin.optimized.kt
// Optimized Subarray Sum Equals K using Prefix Sum and Hash Map
// O(n) time average, O(n) space
/**
* Optimized approach: Use prefix sums to represent cumulative sum up to each index.
* Maintain a hash map of prefixSum -> frequency.
* For each index, check if (currentPrefix - k) exists in map, adding its frequency to count.
* Update map after check to avoid invalid self-counts.
*
* Why this solution:
* - Prefix sums allow O(1) subarray sum computation via subtraction.
* - Hash map enables O(1) lookups for previous prefixes where difference == k.
* - Handles negative numbers and zeros seamlessly, unlike sliding window.
*
* Where to use:
* - Large arrays (up to 2e4) as per constraints, efficient in time.
* - When counting all subarrays with exact sum is needed.
*
* Complexity:
* - Time: O(n) - Single pass through array, each operation (add, check, update) is O(1) amortized.
* - Space: O(n) - Hash map can store up to n unique prefix sums in worst case.
*
* Interview notes:
* - Explain prefix sum concept: sum[i..j] = prefix[j] - prefix[i-1].
* - Highlight initializing map with {0:1} for subarrays starting at index 0.
* - Discuss why order matters: check before update to prevent counting current prefix incorrectly.
* - Compare to brute: from O(n^2) to O(n), big win for large n.
* - In Kotlin, use mutableMapOf<Int, Int>() for integer keys, handles negatives.
*
* Edge cases handled:
* - Empty array: loop doesn't run, count=0.
* - k=0: correctly counts subarrays summing to 0, including single 0s.
* - Negatives: prefix can be negative, map handles it.
* - Duplicate prefixes: frequency counts multiple occurrences.
*/
class Solution {
fun subarraySum(nums: IntArray, k: Int): Int {
val prefixMap = mutableMapOf<Int, Int>() // Mutable map for prefixSum -> frequency
prefixMap[0] = 1 // Initialize for subarrays starting at 0
var prefixSum = 0 // Current cumulative sum
var count = 0 // Result counter
for (num in nums) {
prefixSum += num // Update prefix sum
// Check if (prefixSum - k) exists before updating map
if (prefixMap.containsKey(prefixSum - k)) {
count += prefixMap[prefixSum - k]!! // Add frequency of matching prefixes
}
// Update map with current prefixSum
prefixMap[prefixSum] = prefixMap.getOrDefault(prefixSum, 0) + 1
}
return count
}
}
fun main() {
val sol = Solution()
println(sol.subarraySum(intArrayOf(1,1,1), 2)) // 2
println(sol.subarraySum(intArrayOf(1,2,3), 3)) // 2
println(sol.subarraySum(intArrayOf(1,-1,0), 0)) // 2
println(sol.subarraySum(intArrayOf(), 0)) // 0
println(sol.subarraySum(intArrayOf(0), 0)) // 1
}
object Solution {
def subarraySum(nums: Array[Int], k: Int): Int = {
if (nums.isEmpty) return 0
var count = 0
for (i <- nums.indices) {
var currentSum = 0
for (j <- i until nums.length) {
currentSum += nums(j)
if (currentSum == k) {
count += 1
}
}
}
count
}
}
object Main extends App {
println(Solution.subarraySum(Array(1, 1, 1), 2))
println(Solution.subarraySum(Array(1, 2, 3), 3))
println(Solution.subarraySum(Array(1, -1, 0), 0))
println(Solution.subarraySum(Array(), 0))
println(Solution.subarraySum(Array(0), 0))
}
// File: scala.brute.scala
// Brute-force Subarray Sum Equals K
// O(n^2) time, O(1) extra space (n = nums.length)
/**
* Brute-force approach: Iterate over all possible subarrays and compute their sums.
* For each starting index i, accumulate sum from i to j and check if it equals k.
* This ensures correctness but is inefficient for large n due to quadratic time.
*
* Why this solution:
* - Directly checks every contiguous subarray, guaranteeing all valid ones are counted.
* - No additional data structures needed, simple to implement and understand.
*
* Where to use:
* - Small arrays (n <= 1000) or to demonstrate baseline correctness in interviews.
* - When optimizing for space over time.
*
* Complexity:
* - Time: O(n^2) - Two nested loops: outer for start, inner for end, summing in O(1) per step with accumulation.
* - Space: O(1) - Only a few variables for sum and count.
*
* Interview notes:
* - Start with this in interviews to show you understand the problem definition.
* - Explain why it's slow: for n=2e4, it does ~2e8 operations, which may timeout.
* - Transition to optimized prefix sum approach for better performance.
* - Handles negatives/zeros correctly since it recomputes sums each time.
*
* Edge cases handled:
* - Empty array: loops don't run, count=0.
* - Single element: checked if nums[0] == k.
* - All zeros, k=0: counts all non-empty subarrays.
*/
object Solution {
def subarraySum(nums: Array[Int], k: Int): Int = {
if (nums.isEmpty) return 0 // Early return for empty array
var count = 0
for (i <- nums.indices) { // Outer loop: start of subarray
var currentSum = 0 // Reset sum for each new start
for (j <- i until nums.length) { // Inner loop: end of subarray
currentSum += nums(j) // Accumulate sum incrementally (O(1) per addition)
if (currentSum == k) { // Check after each addition
count += 1 // Increment if match found
}
}
}
count
}
}
// Test runner
object Main extends App {
println(Solution.subarraySum(Array(1, 1, 1), 2)) // 2
println(Solution.subarraySum(Array(1, 2, 3), 3)) // 2
println(Solution.subarraySum(Array(1, -1, 0), 0)) // 2
println(Solution.subarraySum(Array(), 0)) // 0
println(Solution.subarraySum(Array(0), 0)) // 1
}
import scala.collection.mutable
object Solution {
def subarraySum(nums: Array[Int], k: Int): Int = {
val prefixMap = mutable.Map[Long, Int](0L -> 1)
var prefixSum: Long = 0
var count = 0
for (num <- nums) {
prefixSum += num
prefixMap.get(prefixSum - k).foreach { freq =>
count += freq
}
prefixMap(prefixSum) = prefixMap.getOrElse(prefixSum, 0) + 1
}
count
}
}
object Main extends App {
println(Solution.subarraySum(Array(1, 1, 1), 2))
println(Solution.subarraySum(Array(1, 2, 3), 3))
println(Solution.subarraySum(Array(1, -1, 0), 0))
println(Solution.subarraySum(Array(), 0))
println(Solution.subarraySum(Array(0), 0))
}
// File: scala.optimized.scala
// Optimized Subarray Sum Equals K using Prefix Sum and Hash Map
// O(n) time average, O(n) space
/*
Optimized approach: Use prefix sums to represent cumulative sum up to each index.
Maintain a mutable Map of prefixSum -> frequency.
For each index, check if (currentPrefix - k) exists in map, adding its frequency to count.
Update map after check to avoid invalid self-counts.
Why this solution:
- Prefix sums allow O(1) subarray sum computation via subtraction.
- Hash map enables O(1) lookups for previous prefixes where difference == k.
- Handles negative numbers and zeros seamlessly, unlike sliding window.
Where to use:
- Large arrays (up to 2e4) as per constraints, efficient in time.
- When counting all subarrays with exact sum is needed.
Complexity:
- Time: O(n) - Single pass through array, each operation (add, check, update) is O(1) amortized.
- Space: O(n) - Map can store up to n unique prefix sums in worst case.
Interview notes:
- Explain prefix sum concept: sum[i..j] = prefix[j] - prefix[i-1].
- Highlight initializing map with (0 -> 1) for subarrays starting at index 0.
- Discuss why order matters: check before update to prevent counting current prefix incorrectly.
- Compare to brute: from O(n^2) to O(n), big win for large n.
- In Scala, use scala.collection.mutable.Map[Long, Int] for large/negative sums.
Edge cases handled:
- Empty array: loop doesn't run, count=0.
- k=0: correctly counts subarrays summing to 0, including single 0s.
- Negatives: prefix can be negative, map handles it.
- Duplicate prefixes: frequency counts multiple occurrences.
*/
import scala.collection.mutable
object Solution {
def subarraySum(nums: Array[Int], k: Int): Int = {
val prefixMap = mutable.Map[Long, Int](0L -> 1) // Initialize for subarrays starting at 0
var prefixSum: Long = 0 // Current cumulative sum
var count = 0 // Result counter
for (num <- nums) {
prefixSum += num // Update prefix sum
// Check if (prefixSum - k) exists before updating map
prefixMap.get(prefixSum - k).foreach { freq =>
count += freq // Add frequency of matching prefixes
}
// Update map with current prefixSum
prefixMap(prefixSum) = prefixMap.getOrElse(prefixSum, 0) + 1
}
count
}
}
// Test runner
object Main extends App {
println(Solution.subarraySum(Array(1, 1, 1), 2)) // 2
println(Solution.subarraySum(Array(1, 2, 3), 3)) // 2
println(Solution.subarraySum(Array(1, -1, 0), 0)) // 2
println(Solution.subarraySum(Array(), 0)) // 0
println(Solution.subarraySum(Array(0), 0)) // 1
}
struct Solution;
impl Solution {
pub fn subarray_sum(nums: Vec<i32>, k: i32) -> i32 {
if nums.is_empty() {
return 0;
}
let mut count = 0;
for i in 0..nums.len() {
let mut current_sum = 0;
for j in i..nums.len() {
current_sum += nums[j];
if current_sum == k {
count += 1;
}
}
}
count
}
}
fn main() {
println!("{}", Solution::subarray_sum(vec![1, 1, 1], 2));
println!("{}", Solution::subarray_sum(vec![1, 2, 3], 3));
println!("{}", Solution::subarray_sum(vec![1, -1, 0], 0));
println!("{}", Solution::subarray_sum(vec![], 0));
println!("{}", Solution::subarray_sum(vec![0], 0));
}
// File: rust.brute.rs
// Brute-force Subarray Sum Equals K
// O(n^2) time, O(1) extra space (n = nums.len())
/*
Brute-force approach: Iterate over all possible subarrays and compute their sums.
For each starting index i, accumulate sum from i to j and check if it equals k.
This ensures correctness but is inefficient for large n due to quadratic time.
Why this solution:
- Directly checks every contiguous subarray, guaranteeing all valid ones are counted.
- No additional data structures needed, simple to implement and understand.
Where to use:
- Small arrays (n <= 1000) or to demonstrate baseline correctness in interviews.
- When optimizing for space over time.
Complexity:
- Time: O(n^2) - Two nested loops: outer for start, inner for end, summing in O(1) per step with accumulation.
- Space: O(1) - Only a few variables for sum and count.
Interview notes:
- Start with this in interviews to show you understand the problem definition.
- Explain why it's slow: for n=2e4, it does ~2e8 operations, which may timeout.
- Transition to optimized prefix sum approach for better performance.
- Handles negatives/zeros correctly since it recomputes sums each time.
Edge cases handled:
- Empty array: loops don't run, count=0.
- Single element: checked if nums[0] == k.
- All zeros, k=0: counts all non-empty subarrays.
*/
struct Solution;
impl Solution {
pub fn subarray_sum(nums: Vec<i32>, k: i32) -> i32 {
if nums.is_empty() {
return 0; // Early return for empty array
}
let mut count = 0;
for i in 0..nums.len() { // Outer loop: start of subarray
let mut current_sum = 0; // Reset sum for each new start
for j in i..nums.len() { // Inner loop: end of subarray
current_sum += nums[j]; // Accumulate sum incrementally (O(1) per addition)
if current_sum == k { // Check after each addition
count += 1; // Increment if match found
}
}
}
count
}
}
// Test runner
fn main() {
println!("{}", Solution::subarray_sum(vec![1, 1, 1], 2)); // 2
println!("{}", Solution::subarray_sum(vec![1, 2, 3], 3)); // 2
println!("{}", Solution::subarray_sum(vec![1, -1, 0], 0)); // 2
println!("{}", Solution::subarray_sum(vec![], 0)); // 0
println!("{}", Solution::subarray_sum(vec![0], 0)); // 1
}
use std::collections::HashMap;
struct Solution;
impl Solution {
pub fn subarray_sum(nums: Vec<i32>, k: i32) -> i32 {
let mut prefix_map: HashMap<i64, i32> = HashMap::new();
prefix_map.insert(0, 1);
let mut prefix_sum: i64 = 0;
let mut count = 0;
for num in nums {
prefix_sum += num as i64;
if let Some(&freq) = prefix_map.get(&(prefix_sum - k as i64)) {
count += freq;
}
*prefix_map.entry(prefix_sum).or_insert(0) += 1;
}
count
}
}
fn main() {
println!("{}", Solution::subarray_sum(vec![1, 1, 1], 2));
println!("{}", Solution::subarray_sum(vec![1, 2, 3], 3));
println!("{}", Solution::subarray_sum(vec![1, -1, 0], 0));
println!("{}", Solution::subarray_sum(vec![], 0));
println!("{}", Solution::subarray_sum(vec![0], 0));
}
// File: rust.optimized.rs
// Optimized Subarray Sum Equals K using Prefix Sum and Hash Map
// O(n) time average, O(n) space
/*
Optimized approach: Use prefix sums to represent cumulative sum up to each index.
Maintain a HashMap of prefixSum -> frequency.
For each index, check if (currentPrefix - k) exists in map, adding its frequency to count.
Update map after check to avoid invalid self-counts.
Why this solution:
- Prefix sums allow O(1) subarray sum computation via subtraction.
- Hash map enables O(1) lookups for previous prefixes where difference == k.
- Handles negative numbers and zeros seamlessly, unlike sliding window.
Where to use:
- Large arrays (up to 2e4) as per constraints, efficient in time.
- When counting all subarrays with exact sum is needed.
Complexity:
- Time: O(n) - Single pass through array, each operation (add, check, update) is O(1) amortized.
- Space: O(n) - HashMap can store up to n unique prefix sums in worst case.
Interview notes:
- Explain prefix sum concept: sum[i..j] = prefix[j] - prefix[i-1].
- Highlight initializing map with {0:1} for subarrays starting at index 0.
- Discuss why order matters: check before update to prevent counting current prefix incorrectly.
- Compare to brute: from O(n^2) to O(n), big win for large n.
- In Rust, use HashMap<i64, i32> for large/negative sums to handle constraints.
Edge cases handled:
- Empty array: loop doesn't run, count=0.
- k=0: correctly counts subarrays summing to 0, including single 0s.
- Negatives: prefix can be negative, map handles it.
- Duplicate prefixes: frequency counts multiple occurrences.
*/
use std::collections::HashMap;
struct Solution;
impl Solution {
pub fn subarray_sum(nums: Vec<i32>, k: i32) -> i32 {
let mut prefix_map: HashMap<i64, i32> = HashMap::new(); // Use i64 for large sums
prefix_map.insert(0, 1); // Initialize for subarrays starting at 0
let mut prefix_sum: i64 = 0; // Current cumulative sum
let mut count = 0; // Result counter
for num in nums {
prefix_sum += num as i64; // Update prefix sum
// Check if (prefixSum - k) exists before updating map
if let Some(&freq) = prefix_map.get(&(prefix_sum - k as i64)) {
count += freq; // Add frequency of matching prefixes
}
// Update map with current prefixSum
*prefix_map.entry(prefix_sum).or_insert(0) += 1;
}
count
}
}
// Test runner
fn main() {
println!("{}", Solution::subarray_sum(vec![1, 1, 1], 2)); // 2
println!("{}", Solution::subarray_sum(vec![1, 2, 3], 3)); // 2
println!("{}", Solution::subarray_sum(vec![1, -1, 0], 0)); // 2
println!("{}", Solution::subarray_sum(vec![], 0)); // 0
println!("{}", Solution::subarray_sum(vec![0], 0)); // 1
}
class Solution {
function subarraySum($nums, $k) {
if (empty($nums)) return 0;
$count = 0;
for ($i = 0; $i < count($nums); $i++) {
$currentSum = 0;
for ($j = $i; $j < count($nums); $j++) {
$currentSum += $nums[$j];
if ($currentSum == $k) {
$count++;
}
}
}
return $count;
}
}
$sol = new Solution();
echo $sol->subarraySum([1, 1, 1], 2) . "\n";
echo $sol->subarraySum([1, 2, 3], 3) . "\n";
echo $sol->subarraySum([1, -1, 0], 0) . "\n";
echo $sol->subarraySum([], 0) . "\n";
echo $sol->subarraySum([0], 0) . "\n";
// File: php.brute.php
// Brute-force Subarray Sum Equals K
// O(n^2) time, O(1) extra space (n = count($nums))
/**
* Brute-force approach: Iterate over all possible subarrays and compute their sums.
* For each starting index i, accumulate sum from i to j and check if it equals k.
* This ensures correctness but is inefficient for large n due to quadratic time.
*
* Why this solution:
* - Directly checks every contiguous subarray, guaranteeing all valid ones are counted.
* - No additional data structures needed, simple to implement and understand.
*
* Where to use:
* - Small arrays (n <= 1000) or to demonstrate baseline correctness in interviews.
* - When optimizing for space over time.
*
* Complexity:
* - Time: O(n^2) - Two nested loops: outer for start, inner for end, summing in O(1) per step with accumulation.
* - Space: O(1) - Only a few variables for sum and count.
*
* Interview notes:
* - Start with this in interviews to show you understand the problem definition.
* - Explain why it's slow: for n=2e4, it does ~2e8 operations, which may timeout.
* - Transition to optimized prefix sum approach for better performance.
* - Handles negatives/zeros correctly since it recomputes sums each time.
*
* Edge cases handled:
* - Empty array: loops don't run, count=0.
* - Single element: checked if nums[0] == k.
* - All zeros, k=0: counts all non-empty subarrays.
*/
class Solution {
/**
* @param Integer[] $nums
* @param Integer $k
* @return Integer
*/
function subarraySum($nums, $k) {
if (empty($nums)) return 0; // Early return for empty array
$count = 0;
for ($i = 0; $i < count($nums); $i++) { // Outer loop: start of subarray
$currentSum = 0; // Reset sum for each new start
for ($j = $i; $j < count($nums); $j++) { // Inner loop: end of subarray
$currentSum += $nums[$j]; // Accumulate sum incrementally (O(1) per addition)
if ($currentSum == $k) { // Check after each addition
$count++; // Increment if match found
}
}
}
return $count;
}
}
// Test runner
$sol = new Solution();
echo $sol->subarraySum([1, 1, 1], 2) . "\n"; // 2
echo $sol->subarraySum([1, 2, 3], 3) . "\n"; // 2
echo $sol->subarraySum([1, -1, 0], 0) . "\n"; // 2
echo $sol->subarraySum([], 0) . "\n"; // 0
echo $sol->subarraySum([0], 0) . "\n"; // 1
class Solution {
function subarraySum($nums, $k) {
$prefixMap = [0 => 1];
$prefixSum = 0;
$count = 0;
foreach ($nums as $num) {
$prefixSum += $num;
if (isset($prefixMap[$prefixSum - $k])) {
$count += $prefixMap[$prefixSum - $k];
}
$prefixMap[$prefixSum] = ($prefixMap[$prefixSum] ?? 0) + 1;
}
return $count;
}
}
$sol = new Solution();
echo $sol->subarraySum([1, 1, 1], 2) . "\n";
echo $sol->subarraySum([1, 2, 3], 3) . "\n";
echo $sol->subarraySum([1, -1, 0], 0) . "\n";
echo $sol->subarraySum([], 0) . "\n";
echo $sol->subarraySum([0], 0) . "\n";
// File: php.optimized.php
// Optimized Subarray Sum Equals K using Prefix Sum and Hash Map
// O(n) time average, O(n) space
/**
* Optimized approach: Use prefix sums to represent cumulative sum up to each index.
* Maintain an array (hash map) of prefixSum => frequency.
* For each index, check if (currentPrefix - k) exists in map, adding its frequency to count.
* Update map after check to avoid invalid self-counts.
*
* Why this solution:
* - Prefix sums allow O(1) subarray sum computation via subtraction.
* - Hash map enables O(1) lookups for previous prefixes where difference == k.
* - Handles negative numbers and zeros seamlessly, unlike sliding window.
*
* Where to use:
* - Large arrays (up to 2e4) as per constraints, efficient in time.
* - When counting all subarrays with exact sum is needed.
*
* Complexity:
* - Time: O(n) - Single pass through array, each operation (add, check, update) is O(1) amortized.
* - Space: O(n) - Array can store up to n unique prefix sums in worst case.
*
* Interview notes:
* - Explain prefix sum concept: sum[i..j] = prefix[j] - prefix[i-1].
* - Highlight initializing map with [0 => 1] for subarrays starting at index 0.
* - Discuss why order matters: check before update to prevent counting current prefix incorrectly.
* - Compare to brute: from O(n^2) to O(n), big win for large n.
* - In PHP, use array for integer keys, handles negatives safely.
*
* Edge cases handled:
* - Empty array: loop doesn't run, count=0.
* - k=0: correctly counts subarrays summing to 0, including single 0s.
* - Negatives: prefix can be negative, array handles it.
* - Duplicate prefixes: frequency counts multiple occurrences.
*/
class Solution {
/**
* @param Integer[] $nums
* @param Integer $k
* @return Integer
*/
function subarraySum($nums, $k) {
$prefixMap = [0 => 1]; // Initialize for subarrays starting at 0
$prefixSum = 0; // Current cumulative sum
$count = 0; // Result counter
foreach ($nums as $num) {
$prefixSum += $num; // Update prefix sum
// Check if (prefixSum - k) exists before updating map
if (isset($prefixMap[$prefixSum - $k])) {
$count += $prefixMap[$prefixSum - $k]; // Add frequency of matching prefixes
}
// Update map with current prefixSum
$prefixMap[$prefixSum] = ($prefixMap[$prefixSum] ?? 0) + 1;
}
return $count;
}
}
// Test runner
$sol = new Solution();
echo $sol->subarraySum([1, 1, 1], 2) . "\n"; // 2
echo $sol->subarraySum([1, 2, 3], 3) . "\n"; // 2
echo $sol->subarraySum([1, -1, 0], 0) . "\n"; // 2
echo $sol->subarraySum([], 0) . "\n"; // 0
echo $sol->subarraySum([0], 0) . "\n"; // 1
class Solution {
int subarraySum(List<int> nums, int k) {
if (nums.isEmpty) return 0;
int count = 0;
for (int i = 0; i < nums.length; i++) {
int currentSum = 0;
for (int j = i; j < nums.length; j++) {
currentSum += nums[j];
if (currentSum == k) {
count++;
}
}
}
return count;
}
}
void main() {
final sol = Solution();
print(sol.subarraySum([1, 1, 1], 2));
print(sol.subarraySum([1, 2, 3], 3));
print(sol.subarraySum([1, -1, 0], 0));
print(sol.subarraySum([], 0));
print(sol.subarraySum([0], 0));
}
// File: dart.brute.dart
// Brute-force Subarray Sum Equals K
// O(n^2) time, O(1) extra space (n = nums.length)
/**
* Brute-force approach: Iterate over all possible subarrays and compute their sums.
* For each starting index i, accumulate sum from i to j and check if it equals k.
* This ensures correctness but is inefficient for large n due to quadratic time.
*
* Why this solution:
* - Directly checks every contiguous subarray, guaranteeing all valid ones are counted.
* - No additional data structures needed, simple to implement and understand.
*
* Where to use:
* - Small arrays (n <= 1000) or to demonstrate baseline correctness in interviews.
* - When optimizing for space over time.
*
* Complexity:
* - Time: O(n^2) - Two nested loops: outer for start, inner for end, summing in O(1) per step with accumulation.
* - Space: O(1) - Only a few variables for sum and count.
*
* Interview notes:
* - Start with this in interviews to show you understand the problem definition.
* - Explain why it's slow: for n=2e4, it does ~2e8 operations, which may timeout.
* - Transition to optimized prefix sum approach for better performance.
* - Handles negatives/zeros correctly since it recomputes sums each time.
*
* Edge cases handled:
* - Empty array: loops don't run, count=0.
* - Single element: checked if nums[0] == k.
* - All zeros, k=0: counts all non-empty subarrays.
*/
class Solution {
int subarraySum(List<int> nums, int k) {
if (nums.isEmpty) return 0; // Early return for empty array
int count = 0;
for (int i = 0; i < nums.length; i++) { // Outer loop: start of subarray
int currentSum = 0; // Reset sum for each new start
for (int j = i; j < nums.length; j++) { // Inner loop: end of subarray
currentSum += nums[j]; // Accumulate sum incrementally (O(1) per addition)
if (currentSum == k) { // Check after each addition
count++; // Increment if match found
}
}
}
return count;
}
}
// Test runner
void main() {
final sol = Solution();
print(sol.subarraySum([1, 1, 1], 2)); // 2
print(sol.subarraySum([1, 2, 3], 3)); // 2
print(sol.subarraySum([1, -1, 0], 0)); // 2
print(sol.subarraySum([], 0)); // 0
print(sol.subarraySum([0], 0)); // 1
}
class Solution {
int subarraySum(List<int> nums, int k) {
final prefixMap = <int, int>{0: 1};
int prefixSum = 0;
int count = 0;
for (final num in nums) {
prefixSum += num;
if (prefixMap.containsKey(prefixSum - k)) {
count += prefixMap[prefixSum - k]!;
}
prefixMap[prefixSum] = (prefixMap[prefixSum] ?? 0) + 1;
}
return count;
}
}
void main() {
final sol = Solution();
print(sol.subarraySum([1, 1, 1], 2));
print(sol.subarraySum([1, 2, 3], 3));
print(sol.subarraySum([1, -1, 0], 0));
print(sol.subarraySum([], 0));
print(sol.subarraySum([0], 0));
}
// File: dart.optimized.dart
// Optimized Subarray Sum Equals K using Prefix Sum and Hash Map
// O(n) time average, O(n) space
/**
* Optimized approach: Use prefix sums to represent cumulative sum up to each index.
* Maintain a map of prefixSum -> frequency.
* For each index, check if (currentPrefix - k) exists in map, adding its frequency to count.
* Update map after check to avoid invalid self-counts.
*
* Why this solution:
* - Prefix sums allow O(1) subarray sum computation via subtraction.
* - Hash map enables O(1) lookups for previous prefixes where difference == k.
* - Handles negative numbers and zeros seamlessly, unlike sliding window.
*
* Where to use:
* - Large arrays (up to 2e4) as per constraints, efficient in time.
* - When counting all subarrays with exact sum is needed.
*
* Complexity:
* - Time: O(n) - Single pass through array, each operation (add, check, update) is O(1) amortized.
* - Space: O(n) - Map can store up to n unique prefix sums in worst case.
*
* Interview notes:
* - Explain prefix sum concept: sum[i..j] = prefix[j] - prefix[i-1].
* - Highlight initializing map with {0:1} for subarrays starting at index 0.
* - Discuss why order matters: check before update to prevent counting current prefix incorrectly.
* - Compare to brute: from O(n^2) to O(n), big win for large n.
* - In Dart, use Map<int, int> for integer keys, handles negatives safely.
*
* Edge cases handled:
* - Empty array: loop doesn't run, count=0.
* - k=0: correctly counts subarrays summing to 0, including single 0s.
* - Negatives: prefix can be negative, map handles it.
* - Duplicate prefixes: frequency counts multiple occurrences.
*/
class Solution {
int subarraySum(List<int> nums, int k) {
final prefixMap = <int, int>{0: 1}; // Initialize for subarrays starting at 0
int prefixSum = 0; // Current cumulative sum
int count = 0; // Result counter
for (final num in nums) {
prefixSum += num; // Update prefix sum
// Check if (prefixSum - k) exists before updating map
if (prefixMap.containsKey(prefixSum - k)) {
count += prefixMap[prefixSum - k]!; // Add frequency of matching prefixes
}
// Update map with current prefixSum
prefixMap[prefixSum] = (prefixMap[prefixSum] ?? 0) + 1;
}
return count;
}
}
// Test runner
void main() {
final sol = Solution();
print(sol.subarraySum([1, 1, 1], 2)); // 2
print(sol.subarraySum([1, 2, 3], 3)); // 2
print(sol.subarraySum([1, -1, 0], 0)); // 2
print(sol.subarraySum([], 0)); // 0
print(sol.subarraySum([0], 0)); // 1
}
