Задача: 523. Continuous Subarray Sum
Сложность: medium

Дан целочисленный массив nums и целое число k. Верните true, если в nums есть хорошая подмассив, или false в противном случае.
Хороший подмассив — это подмассив, который:
имеет длину не менее двух, и
сумма элементов подмассива является кратной k.
Учтите:
Подмассив — это непрерывная часть массива.
Целое число x является кратным k, если существует целое число n такое, что x = n * k. Число 0 всегда является кратным k.

Пример:

Input: nums = [23,2,4,6,7], k = 6
Output: true
Explanation: [2, 4] is a continuous subarray of size 2 whose elements sum up to 6.

👨‍💻 Алгоритм:

1⃣Инициализируйте целое число prefixMod = 0 и хеш-таблицу modSeen. Инициализируйте modSeen[0] значением -1, чтобы учесть начальное значение prefixMod.

2⃣Итеративно пройдите по всем элементам массива nums.

3⃣Вычислите prefixMod как (prefixMod + nums[i]) % k. Если prefixMod существует в хеш-таблице: Если размер самого длинного подмассива с модулем k составляет не менее 2, верните true. Если prefixMod не существует в хеш-таблице: Установите modSeen[prefixMod] = i. Если после завершения итерации не найден хороший подмассив, верните false.

😎 Решение:

class Solution {
    function checkSubarraySum($nums, $k) {
        $prefixMod = 0;
        $modSeen = [0 => -1];
        
        for ($i = 0; $i < count($nums); $i++) {
            $prefixMod = ($prefixMod + $nums[$i]) % $k;
            
            if (array_key_exists($prefixMod, $modSeen)) {
                if ($i - $modSeen[$prefixMod] > 1) {
                    return true;
                }
            } else {
                $modSeen[$prefixMod] = $i;
            }
        }
        
        return false;
    }
}

Ставь 👍 и забирай 📚 Базу знаний