Back to Arrays & Hashing
Medium
Subarray Sum Equals K
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.
Examples
Input:nums = [1,1,1], k = 2
Output:2
There are two subarrays that sum to 2: nums[0..1] and nums[1..2].
Input:nums = [1,2,3], k = 3
Output:2
There are two subarrays that sum to 3: [1,2] and [3].
Constraints
1 <= nums.length <= 2 * 10^4-1000 <= nums[i] <= 1000-10^7 <= k <= 10^7
Approach
Create a prefix sum array. Then use two nested loops to check every possible subarray (from index i to j). The sum of the subarray is `prefix[j] - prefix[i-1]`. If it equals k, increment the count. We can optimize space by maintaining the running sum in the inner loop instead of a separate prefix array.
Complexity Analysis
Time Complexity
O(n^2)
Space Complexity
O(1)
This approach might result in Time Limit Exceeded (TLE) for large inputs because of the O(n^2) time complexity.
Solution.java
class Solution { public int subarraySum(int[] nums, int k) { int count = 0; for (int start = 0; start < nums.length; start++) { int sum = 0; for (int end = start; end < nums.length; end++) { sum += nums[end]; if (sum == k) { count++; } } } return count; }}