Problem

Given an array of integers and a target sum (K), find a contiguous subarray whose sum is equal to the given target sum (K). If there are multiple such subarrays, returning any one of them is sufficient. If no such subarray exists, return an empty list.

Examples

Example 1:

1
2
3

Input: arr = [1, 2, 3, 4, 5], target = 9
Output: [2, 3, 4]
Explanation: The subarray [2, 3, 4] has a sum equal to 9.

Example 2:

1
2
3

Input: arr = [1, -1, 5, -2, 3], target = 3
Output: [1, -1, 5, -2]
Explanation: The subarray [1, -1, 5, -2] has a sum equal to 3.

Example 3:

1
2
3

Input: arr = [1, 2, 3], target = 10
Output: []
Explanation: There is no subarray with a sum equal to 10.

Solution

Method 1 - Naive

Naive approach is to generate all subarrays using nested loops, and check which subarray sum matches target. Time complexity - O(n^2)

Method 2 - Sliding Window Technique

Here is the approach:

  1. Use a sliding window (two-pointer) technique to find the subarray.
  2. Initialize two pointers start and end.
  3. Maintain a variable current_sum to store the sum of the current subarray.
  4. Expand the window by moving the end pointer to the right and update current_sum.
  5. If current_sum exceeds the target, shrink the window by moving the start pointer to the right until current_sum is less than or equal to the target.
  6. If current_sum equals the target, return the subarray.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

public class Solution {
    public static List<Integer> subarraySumEqualsK(int[] arr, int target) {
        int start = 0;
        int currentSum = 0;

        for (int end = 0; end < arr.length; end++) {
            currentSum += arr[end];

            while (currentSum > target && start <= end) {
                currentSum -= arr[start];
                start++;
            }

            if (currentSum == target) {
                List<Integer> result = new ArrayList<>();
                for (int i = start; i <= end; i++) {
                    result.add(arr[i]);
                }
                return result;
            }
        }

        return new ArrayList<>();
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

def subarray_sum_equals_k(arr, target):
    start = 0
    current_sum = 0

    for end in range(len(arr)):
        current_sum += arr[end]

        while current_sum > target and start <= end:
            current_sum -= arr[start]
            start += 1

        if current_sum == target:
            return arr[start : end + 1]

    return []

Complexity

  • ⏰ Time complexity: O(n), where (n) is the length of the array. Each element is processed at most twice.
  • 🧺 Space complexity: O(1), for the sliding window approach, not including the space required for the output subarray.