Код элемента: Непрерывная Сумма Подмассивов

523. Непрерывная Сумма Подмассивов

Проблема:

Учитывая список неотрицательных чисел и целевое целое число k, напишите функцию, чтобы проверить, имеет ли массив непрерывный подмассив размером не менее 2, который суммируется до кратного k, то есть суммируется до n * k, где n также является целым числом.

Пример 1:

Ввод: [23, 2, 4, 6, 7], Результат: Истинное объяснение: Потому что [2, 4] является непрерывным подмассивом размера 2 и суммируется до 6.

Пример 2:

Ввод: [23, 2, 6, 4, 7], Результат: Истинное объяснение: Потому что [23, 2, 6, 4, 7] представляет собой непрерывный подмассив размером 5 и суммируется до 42.

Ограничения:

Длина массива не будет превышать 10 000. Вы можете предположить, что сумма всех чисел находится в диапазоне 32-разрядного целого числа со знаком.

Решение

В задачах с непрерывным подмассивом обычно требуется определить, существует ли непрерывный подмассив в массиве nums минимальной длины “l”, которая кратна заданной цели K

Для любого массива чисел с длиной n и индексами в порядке 0, i, j – где o < i < j < n [0, …., i, …., j, … n-1]

• Рассмотрим элементы от 0-го индекса до i-го индекса. (цифры[0]+…..+ числа[i]) и суммы, деленной на K (т.е. % K)
• Рассмотрим элементы от 0-го индекса до j-го индекса. ((цифры[0]+…..+ числа[j]) суммы, деленной на K (т.е. % K)

• По теореме об остатках , Учитывая любое целое число A и положительное целое число B, существуют уникальные целые числа Q и R, такие, что * Q + R, где 0 ≤ R < B

  Выражаясь математическими терминами, Текущая сумма от первого элемента до индекса i (сумма) при делении на K, modI_K и SUMI могут быть записаны как сумма * x + modI_K Текущая сумма от первого элемента до индекса j (сумма J) при делении на K, модуль J_K и сумма могут быть записаны как сумма J * x + mod_K

  Если моды sumI и sumi равны modI_K это означает, что разница между сумами и сумами приводит к константе, умноженной на K. SUMI – * K Это означает, что должна существовать сумма подмассивов, кратная k.

• Так, чтобы решить проблемы такого рода, нам нужно сохранить остатки текущей суммы, чтобы помочь нам определить, что две текущие суммы имеют дополнительную сумму, кратную K.

    public boolean checkSubarraySum(int[] nums, int k) {
        Map remainderMap = new HashMap<>();

        remainderMap.put(0, -1);
        int runningSum = 0;
        int minLen = 2;

        for(int i = 0; i < nums.length; i++) {
            runningSum += nums[i];
            if(k != 0) {
                runningSum = runningSum % k;
            }
            if(remainderMap.containsKey(runningSum)) {
                if(i - remainderMap.get(runningSum) >= minLen)
                    return true;
            } else {
                remainderMap.put(runningSum, i);
            }
        }
        return false;
    }

Спасибо за чтение:)

Оригинал: “https://dev.to/sphoorthi/leetcode-continuous-subarray-sum-459o”