Subarray Sum Equals K

MEDIUM

Description

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.

Example 1:

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

Example 2:

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

Constraints:

1 <= nums.length <= 2 * 10⁴
-1000 <= nums[i] <= 1000
-10⁷ <= k <= 10⁷

Approaches

Checkout 2 different approaches to solve Subarray Sum Equals K. Click on different approaches to view the approach and algorithm in detail.

Brute Force with Cumulative Sum

The most straightforward approach is to consider every possible subarray, calculate its sum, and check if the sum equals k. We can optimize the sum calculation by iterating through all possible start points and for each start point, extending the subarray to the right while keeping a running sum.

Algorithm

Initialize a counter count to 0.
Use an outer loop with index start from 0 to n-1 to select the starting element of the subarray.
Inside the outer loop, initialize a currentSum to 0.
Use an inner loop with index end from start to n-1. This loop defines the end of the subarray.
In each step of the inner loop, add nums[end] to currentSum. This currentSum represents the sum of the subarray nums[start...end].
If currentSum is equal to k, increment count.
After both loops complete, return count.

This approach iterates through all possible starting points of a subarray. For each starting point, it iterates through all possible ending points, effectively generating every contiguous subarray. A running sum is maintained for the current subarray, and if this sum equals k, a counter is incremented.

public int subarraySum(int[] nums, int k) {
    int count = 0;
    for (int start = 0; start < nums.length; start++) {
        int currentSum = 0;
        for (int end = start; end < nums.length; end++) {
            currentSum += nums[end];
            if (currentSum == k) {
                count++;
            }
        }
    }
    return count;
}

Complexity Analysis

Time Complexity: O(n^2), where n is the length of `nums`. The two nested loops lead to a quadratic runtime, which is too slow for the given constraints.Space Complexity: O(1), as we only use a constant amount of extra space for variables like `count` and `currentSum`.

Pros and Cons

Pros:

Simple to understand and implement.
Requires no extra space (O(1) space complexity).

Cons:

Inefficient time complexity, leading to "Time Limit Exceeded" on larger test cases as per the problem constraints.

Code Solutions

Checking out 3 solutions in different languages for Subarray Sum Equals K. Click on different languages to view the code.

class Solution {
public
  int subarraySum(int[] nums, int k) {
    Map<Integer, Integer> counter = new HashMap<>();
    counter.put(0, 1);
    int ans = 0, s = 0;
    for (int num : nums) {
      s += num;
      ans += counter.getOrDefault(s - k, 0);
      counter.put(s, counter.getOrDefault(s, 0) + 1);
    }
    return ans;
  }
}

Video Solution

Watch the video walkthrough for Subarray Sum Equals K

Patterns:

Prefix Sum

Data Structures:

ArrayHash Table

Companies:

AMD |ByteDance |Capgemini |Cisco |