523. Сумма непрерывного подмассива (Continuous Subarray Sum)

Задание.

Получен целочисленный массив nums и целое число k

Верните true, если у nums есть хороший подмассив, или false в противном случае.

Хороший подмассив – это подмассив, у которого:

• длина равна по меньшей мере двум,

• сумма элементов подмассива кратна k.

Обратите внимание, что:

Подмассив – это непрерывная часть массива.

Целое число x кратно k, если существует целое число n такое, что x = n * k.

0 всегда кратно k.

Пример 1.

Входные данные: nums = [23,2,4,6,7], k = 6

Результат: true

Объяснение: [2, 4] представляет собой непрерывный подмассив размера 2, элементы которого в сумме составляют 6.

Пример 2.

Входные данные: nums = [23,2,6,4,7], k = 6

Результат: true

Объяснение: [23, 2, 6, 4, 7] представляет собой непрерывный подмассив размера 5, сумма элементов которого составляет 42. 42 кратно 6, потому что 42 = 7 * 6, а 7 - целое число.

Пример 3.

Входные данные: nums = [23,2,6,4,7], k = 13

Результат: false

Решение.

class Solution {
public:
    bool checkSubarraySum(vector<int>& nums, int k) {
        unordered_map<int,int>m;
        m[0] = -1;
        int sum = 0, len = nums.size();

        if(k == 0) return false;

        for(int i = 0; i < len; i++) {
            sum += nums[i];
            if(k != 0) {
                sum %= k;
            }

            if(m.count(sum) == 0) {
                // такого остатка от деления не было
                // запоминаем индекс, на котором он встретился
                m[sum] = i;
            } else {
                // такой остаток уже встречался, 
                // это кандидат на успешно найденную последовательность
                // нужно проверить, чтобы разность текущего и ранее встреченного индексов
                // была больше единицы (в последовательности два элемента и больше)
                if(i - m[sum] > 1) return true;
            }
        }
        return false;
    }
};

Способ решения.

Элементы массива nums последовательно складываются, сумма делится на k, определяется остаток от деления.

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

Если данный остаток от деления (sum) встретится ещё раз, то между текущим положением элемента (i) и прежним положением (m[sum]) даст последовательность, которая нацело делится на k.

Например,