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.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


  • 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


  • 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.1

  • 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.1: 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))


  • 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