Найти подмассив из массива, равного некоторому значению X

Question

Фон

Вам дан массив, содержащий положительные и отрицательные числа. Вы должны найти подмассив в массиве, равный некоторому значению X. Входными данными являются массив и значение X. Выходные данные являются начальным и конечным индексом подмассива.

Пример

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

Ниже приведен код, который я нашел на 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); 

ВОПРОС В целом я могу понять, почему это решение работает. Первый блок с условием cur_sum - sum == 0 имеет для меня тотальный смысл.

Однако я очень озадачен тем, почему работает проверка hashMap.containsKey(cur_sum - sum). Я знаю, что это работает каждый раз, но я хочу понять математическое значение этого. Я прочитал в блоге интервью, что в нем используется общая методика сравнения, но я не уверен, как это относится к этому.

Я не пытаюсь запомнить это решение, когда я готовлюсь к собеседованию, но пытаюсь понять, почему оно работает.

Я часами придумывал примеры и прослеживал их вручную, и решение работает, но я не могу понять, почему работает эта техника, и я отказываюсь запоминать ее вслепую.

Например, если мы говорим о массиве только с положительными числами, то я знаю, что можно использовать технику "СКОЛЬЗЯЩЕГО ОКНА" и что я могу полностью понять. Когда вы расширяете окно, сумма увеличивается, а когда вы закрываете окно, сумма уменьшается. Это не относится к проблеме, описанной выше, и поэтому был бы признателен за помощь.

Answer 1

sum - это число, которое мы хотим достичь

cur_sum - это сумма всех элементов в массиве до сих пор

скажи, что cur_sum - sum = x

Каждый шаг мы обновляем cur_sum в начале, и если условие, которое вас смущает, оценивается как false, мы обновляем хэш-карту и продолжаем.

Пока все хорошо.

Теперь, почему мы ищем, если x уже есть в хэш-карте?

Ответ на этот вопрос таков: если существовал предыдущий индекс i, в котором все элементы до этого индекса (включительно) имели сумму x, это означает, что от индекса i+1 до текущего индекса мы иметь подмассив, который суммирует: cur_sum - x

И поскольку мы уже знаем, что cur_sum - sum = x, это означает, что подмассив, начинающийся с i+1 и заканчивающийся текущим индексом, суммируется точно в sum.

Давайте рассмотрим пример, который вы разместили:

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

Давайте итерируем массив:
индекс 0: сумма 2 => обновление карты с (0: 2)
индекс 1: сумма 2 + 6 = 8 => обновить карту с помощью (1: 8)
индекс 2: сумма 2 + 6 + 0 = 8 => обновить карту с помощью (2: 8)
индекс 3: сумма 2 + 6 + 0 + 9 = 17 =>

но теперь мы можем видеть, что карта уже содержит 17-15 = 2 (0: 2) следовательно, мы знаем, что сумма подмассива начинается с индекса 1 (индекс 1 идет после нуля от (0: 2)) и заканчивается с текущим индексом: 3 - этот подмассив суммируется с 15.