560. Subarray Sum Equals K - Detailed Explanation

Problem Statement

Given an integer array nums and an integer k, your task is to find the total number of continuous subarrays whose sum equals to k.

A subarray is a contiguous sequence of elements within an array.

Example 1:

• Input:

  nums = [1, 1, 1], k = 2
  

• Output:

  2
  

• Explanation:
  The subarrays that sum up to 2 are [1, 1] starting at index 0 and [1, 1] starting at index 1.

Example 2:

• Input:

  nums = [1, 2, 3], k = 3
  

• Output:

  2
  

• Explanation:
  The subarrays that sum up to 3 are [1, 2] and [3].

Constraints:

• The length of the array is in the range [1, 20000].
• The range of numbers in the array is [-1000, 1000].
• The value of k is in the range [-10^7, 10^7].

Hints Before Diving into the Solution

1. Brute Force Idea:
   Think about checking all possible subarrays and summing their elements. How many subarrays are there? Can you optimize it?

2. Prefix Sum and HashMap:
   Consider using prefix sums. If you know the sum of all elements up to two different indices, you can compute the sum of the subarray between them in constant time.
   Use a hash map to store the frequencies of prefix sums encountered so far. This will help you quickly determine how many previous subarrays can form a valid subarray ending at the current index.

Approach 1: Brute Force (Not Optimal)

Explanation:

• Idea:
  Check every possible subarray by using two nested loops.
  For each subarray, calculate its sum and check if it equals k.

• Steps:

  1. Iterate over all starting indices.
  2. For each starting index, iterate over all ending indices.
  3. Sum up the elements of the subarray and check if the sum equals k.

• Drawback:
  Time complexity is O(n²) or worse. This approach will not scale well with larger inputs.

Approach 2: Optimal Solution Using Prefix Sum and Hash Map

Overview:

• Prefix Sum Concept:
  A prefix sum at index i is the sum of all elements from the beginning of the array up to i. Denote this as prefixSum[i].

• Key Observation:
  If you have two indices i and j (with i < j) such that:

  prefixSum[j] - prefixSum[i] = k
  

  then the subarray from index i + 1 to j sums to k.

• Using a Hash Map:
  Use a hash map (sumCount) to keep track of how many times a particular prefix sum occurs as you iterate through the array.
  For each new prefix sum, check if currentPrefixSum - k exists in the map. If it does, then there are that many subarrays ending at the current index whose sum is k.

Detailed Walkthrough:

1. Initialization:

   • Set currentPrefixSum = 0.
   • Use a hash map sumCount to store frequency of prefix sums. Initialize it with {0: 1} to account for subarrays that start from index 0.
   • Initialize a counter totalCount to 0.

2. Iteration:

   • For each number in the array:
     • Update the currentPrefixSum by adding the current number.
     • Check if currentPrefixSum - k exists in sumCount. If yes, add its frequency to totalCount because each occurrence represents a valid subarray ending at the current index.
     • Update the hash map with the current prefix sum.

3. Return:
   After processing all elements, totalCount holds the total number of subarrays with sum equal to k.