Find a subarray from a array that equals some value X

Question

Background

You are given an array that includes positive and negative numbers. You are to find a subarray within the array that equals some value X. The input is the array and the X value. The output is the starting and ending index of the subarray.

Example

Array = [2,6,0,9,7,3,1,4,1,10] 
X = 15
Output = [1,3]

Following is the Code I found on geeks4geeks

  public static void subArraySum(int[] arr, int n, int sum) { 
        //cur_sum to keep track of cummulative sum till that point 
        int cur_sum = 0; 
        int start = 0; 
        int end = -1; 
        HashMap<Integer, Integer> hashMap = new HashMap<>(); 

        for (int i = 0; i < n; i++) { 
            cur_sum = cur_sum + arr[i]; 
            //check whether cur_sum - sum = 0, if 0 it means 
            //the sub array is starting from index 0- so stop 
            if (cur_sum - sum == 0) { 
                start = 0; 
                end = i; 
                break; 
            } 
            //if hashMap already has the value, means we already  
            // have subarray with the sum - so stop 
            if (hashMap.containsKey(cur_sum - sum)) { 
                start = hashMap.get(cur_sum - sum) + 1; 
                end = i; 
                break; 
            } 
            //if value is not present then add to hashmap 
            hashMap.put(cur_sum, i); 

        } 
        // if end is -1 : means we have reached end without the sum 
        if (end == -1) { 
            System.out.println("No subarray with given sum exists"); 
        } else { 
            System.out.println("Sum found between indexes " 
                            + start + " to " + end); 

QUESTION Overall I am able to understand why this solution works. The first block with the condition cur_sum - sum == 0 makes total sense to me.

However I am extremely confused about why the hashMap.containsKey(cur_sum - sum) check is working. I know that it works every time but I want to understand the mathematical significance behind it. I read in a interview blog that this uses the common diff technique but i am not sure how this applies to this.

I am not trying to memorize this solution as I prepare for interview but trying to build a solid understanding of why it is working.

I have spent hours coming up with examples and traced through them by hand and the solution works but I am not able to grasp why this technique works and i refuse to memorize it blindly.

For instance if we are talking about a array with positive numbers only then i know the "SLIDING WINDOW" technique can be used and that i am able to completely comprehend. As you expand the window the sum gets larger and as you close the window the sum gets smaller. This is not the case for the problem above and so would appreciate some help.

Answer 1

sum - is the number we want to achieve

cur_sum - is the sum of all the elements in the array so far

say that cur_sum - sum = x

Each step we update cur_sum at the beginning and if the condition that confuses you evaluates to false we update the hashmap and continue.

So far so good.

Now, why are we looking to see if x is already in the hashmap?

The answer to that is that if there was a previous index i which all the elements till that index (inclusive) had the sum of x, this means that from index i+1 till the current index, we have a subarray which sums to: cur_sum - x

And since we already know that cur_sum - sum = x that means that the subarray that starts at i+1 and ends at the current index sums exactly to sum.

Let's take the example you posted:

Array = [2,6,0,9,7,3,1,4,1,10] 
X = 15
Output = [1,3]

Let's iterate the array:
index 0: sum 2 => updating the map with (0:2)
index 1: sum 2+6=8 => updating the map with (1:8)
index 2: sum 2+6+0=8 => updating the map with (2:8)
index 3: sum 2+6+0+9=17 =>

but now we can see that the map already contains 17-15=2 (0:2) hence we know that the sum of the subarray that starts at index 1 (index 1 comes after zero from (0:2)) and ends at the current index: 3 - this subarray sums to 15.