Задача: 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 {
    func checkSubarraySum(_ nums: [Int], _ k: Int) -> Bool {
        var prefixMod = 0
        var modSeen: [Int: Int] = [0: -1]
        
        for i in 0..<nums.count {
            prefixMod = (prefixMod + nums[i]) % k
            
            if let prevIndex = modSeen[prefixMod] {
                if i - prevIndex > 1 {
                    return true
                }
            } else {
                modSeen[prefixMod] = i
            }
        }
        
        return false
    }
}

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