# HelloKoding

Practical coding guides

# Subarray Sum Equals K

In this article, you will learn to resolve the Subarray Sum Equals K problems by using Brute force, Sliding window, and Hash table algorithms

## Problem 1

• Given an unsorted array of non-negative integers `a[n]` and an integer `k`
• Find a continuous subarray whose sum equals to `k`

## Example 1

• Input: a = [4, 0, 11, 6, 1, 7] and k = 8
• Output: [1, 7]

## Approach 1.1: Brute Force

• Consider the sum of every continuous subarray
• Return the first subarray when its sum equals to `k`

SubarrayGivenSumBruteforce.java

``````package com.hellokoding.algorithm;

import java.util.Arrays;

public class SubarrayGivenSumBruteforce {
public static int[] findSubarray(int[] a, int k) {
for(int i = 0; i < a.length; i++) {

int currentSum = a[i];

for(int j = i + 1; j <= a.length; j++) {

if (currentSum == k) {
return Arrays.copyOfRange(a, i, j);
} else if (currentSum > k || j == a.length) {
break;
}

currentSum += a[j];
}
}

return null;
}

public static void main (String[] args) {
int[] a = {4, 0, 11, 6, 1, 7};
int k = 8;
System.out.println(Arrays.toString(findSubarray(a, k)));
}
}
``````
• Time complexity: O(n2) as with each element in the given array, you iterate over the remaining elements to calculate the sum of possible subarrays
• Space complexity: O(1)

## Approach 1.2: Sliding Window

• Find the sliding window sum, say `ws`, in the index range `[i, j]` of the given array `a[n]`, that equals `k` by increasing `j` continuously from `i` to `n-1`
• Return the result as `ws` as soon as it equals `k`, otherwise, reduce `ws` and increase `i`

SubarrayGivenSumWindowSliding.java

``````package com.hellokoding.algorithm;

import java.util.Arrays;

public class SubarrayGivenSumWindowSliding {
public static int[] findSubarray(int[] a, int k) {
int windowSum = 0, i = 0, j = 0;

while (i < a.length) {
while (j < a.length && windowSum < k) {
windowSum += a[j++];
}

if (windowSum == k) {
return Arrays.copyOfRange(a, i, j);
}

windowSum -= a[i++];
}

return null;
}

public static void main (String[] args) {
int[] a = {4, 0, 11, 6, 1, 7};
int k = 8;
System.out.println(Arrays.toString(findSubarray(a, k)));
}
}
``````
• Time complexity: O(n)
• Space complexity: O(1)

## Problem 2

• Given an unsorted array of integers `a[n]` and an integer `k`
• Find the total number of continuous subarrays whose sum equals to `k`

### Example 2

• Input: a = [-4, 12, -11, 6, 1, 7], k = 8
• Output: 3
• Explanation: [-4, 12], [12, -11, 6, 1], [1, 7] are 3 subarrays have sum equals to 8

## Approach 2: Hash table

• Say ci, cj is the cumulative sum at index `i` and `j` in the given array `a[n]`

Elements from `i` to `j` will form a subarray that satify the constraint if cj - k = ci ∀ 0 <= i < j < n

• Use a hash table `h` with key = ci ∀ 0 <= i < n, value = count(ci) in `h`
• The final result is count(h.getValueByKey(ci - k))

SubarrayGivenSumHashtable.java

``````package com.hellokoding.algorithm;

import java.util.HashMap;
import java.util.Map;

public class SubarrayGivenSumHashtable {
public static int countSubArrays(int[] a, int k) {
int count = 0;
int cumulativeSum = 0;
Map<Integer, Integer> map = new HashMap<>();
map.put(0, 1);

for (int value : a) {
cumulativeSum += value;
if (map.containsKey(cumulativeSum - k)) {
count += map.get(cumulativeSum - k);
}

map.put(cumulativeSum, map.getOrDefault(cumulativeSum, 0) + 1);
}

return count;
}

public static void main (String[] args) {
int[] a = {-4, 12, -11, 6, 1, 7};
int k = 8;
System.out.println(countSubArrays(a, k));
}
}
``````
• Time complexity: O(n) as the given array is traversed through only once
• Space complexity: O(n) as the hash table can hold up to `n` elements
Follow HelloKoding