Задача: №18. 4Sum
Сложность: medium

Учитывая массив nums из n целых чисел, верните массив всех уникальных четверок [nums[a], nums[b], nums[c], nums[d]] таких, что:
- 0 <= a, b, c, d < n
- a, b, c и d различны.
- nums[a] + nums[b] + nums[c] + nums[d] == target

Вы можете вернуть ответ в любом порядке.

Пример:

Input: nums = [1,0,-1,0,-2,2], target = 0  
Output: [[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]  

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

1⃣Отсортировать массив для удобного пропуска дубликатов и эффективного поиска.

2⃣Использовать два вложенных цикла для выбора первых двух чисел и два указателя для поиска оставшихся двух чисел.

3⃣Обрабатывать дубликаты, чтобы избежать повторяющихся четверок.

😎 Решение:

class Solution {
    func fourSum(_ nums: [Int], _ target: Int) -> [[Int]] {
        let len = nums.count
        guard len >= 4 else { return [] }
        
        var result = [[Int]]()
        let sort = nums.sorted()
        
        for a in 0..<(len - 3) {
            if a > 0, sort[a] == sort[a - 1] { continue }
            for b in (a + 1)..<(len - 2) {
                if b > a + 1, sort[b] == sort[b - 1] { continue }
                
                var c = b + 1, d = len - 1
                while c < d {
                    let sum = sort[a] + sort[b] + sort[c] + sort[d]
                    if sum == target {
                        result.append([sort[a], sort[b], sort[c], sort[d]])
                        repeat { c += 1 } while c < d && sort[c] == sort[c - 1]
                        repeat { d -= 1 } while c < d && sort[d] == sort[d + 1]
                    } else if sum < target {
                        c += 1
                    } else {
                        d -= 1
                    }
                }
            }
        }
        return result
    }
}

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