Вопрос: Напишите функцию, которая возвращает триплеты, суммирующиеся с заданной целью, или ноль, если они отсутствуют.
Например: [1] и 3, вы должны вернуть nil,
Например, учитывая [2, 4, 5, 6] и 3, вы должны вернуть nil,
Например, учитывая [2, 4, 5, 1] и 7, вы должны вернуть (2, 4, 1)).
Подсказки:
- если длина массива меньше трех, мы не можем найти триплеты,
- Брут for - это тройной цикл for,
- Вы можете сделать это за O(n²) без дополнительного места.
Решение:
func threeSum(array: [Int], sum: Int) -> (Int, Int, Int)? {
// 1.
guard array.count > 2 else { return nil }
// 2.
for i in 0..<array.count {
// 3.
var j = 1
var k = array.count - 1
// 4.
while j < k {
let a = array[i]
let b = array[j]
let c = array[k]
if a + b + c == sum, i != j, i != k {
// 5.
return (a, b, c)
}
// 6.
j += 1
k -= 1
}
}
// 7.
return nil
}
Пояснения:
1. Если элементов меньше трех, триплетов не найти; вернуть ноль.
guard array.count > 2 else { return nil }
2. Пройдемся по всем элементам (индекс i).
for i in 0..<array.count {
3. Давайте используем еще два индекса, j и k, j инициализируется единицей, а k инициализируется последним индексом массива.
var j = 1 var k = array.count - 1
4. Зацикливаемся до тех пор, пока j не будет меньше k.
while j < k {
5. Если три элемента с индексами i, j и k в сумме дают цель, а i, j и k разные индексы, мы нашли тройку, то возвращаем элементы.
let a = array[i]
let b = array[j]
let c = array[k]
if a + b + c == sum, i != j, i != k {
return (a, b, c)
6. В противном случае уменьшите диапазон, увеличив j и уменьшив k.
j += 1 k -= 1
7. Мы не нашли ни одной тройки; вернуть ноль.
return nil
Сложность:
- Временная сложность: поскольку мы повторяем массив n раз, пространственная сложность составляет O (n ^ 2),
- Пространственная сложность: поскольку мы используем только три целых числа, пространственная сложность постоянна O (1).
Тест-кейсы:
public func testThreeSum() {
assert(threeSum(array: [1], sum: 3) == nil, "threeSum 1 not equal")
assert(threeSum(array: [2, 4, 5, 6], sum: 3) == nil, "threeSum 2 not equal")
assert(threeSum(array: [2, 4, 5, 1], sum: 7)! == (2, 4, 1), "threeSum 3 not equal")
}
Следовать за:
Нет дополнительного вопроса.
‹‹ Структуры данных, алгоритмы и вопросы для интервью ››
Повышение уровня кодирования
Спасибо, что являетесь частью нашего сообщества! Перед тем, как ты уйдешь:
- 👏 Хлопайте за историю и подписывайтесь на автора 👉
- 📰 Смотрите больше контента в публикации Level Up Coding
- 💰 Бесплатный курс собеседования по программированию ⇒ Просмотреть курс
- 🔔 Подписывайтесь на нас: Twitter | ЛинкедИн | "Новостная рассылка"
🚀👉 Присоединяйтесь к коллективу талантов Level Up и найдите прекрасную работу
