Swift | LeetCode

Задача: 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
    }
}

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