tgoop.com/golang_interview/1348
Create:
Last Update:
Last Update:
Вам дан массив целых чисел nums. Требуется найти все уникальные тройки (a, b, c), такие что a + b + c = 0. Порядок элементов в тройке не важен, дубликаты недопустимы.
Идея оптимального решения
1. Сортируем массив (O(n log n)), чтобы упростить поиск и контроль дубликатов.
2. Фиксируем первый элемент i, затем две указки l и r («два указателя») пробегают подмассив справа/слева:
Если сумма < 0 → сдвигаем l++,
Если сумма > 0 → сдвигаем r--,
Если сумма == 0 → сохраняем тройку и пропускаем дубликаты вокруг l и r.
3. Пропускаем дубликаты и для i, чтобы не повторять стартовую точку.
Сложность: O(n^2) по времени и O(1) доп. памяти не считая результата.
Реализация:
package main
import (
"fmt"
"sort"
)
func threeSum(nums []int) [][]int {
sort.Ints(nums)
n := len(nums)
res := make([][]int, 0)
for i := 0; i < n; i++ {
// Пропускаем одинаковые стартовые значения
if i > 0 && nums[i] == nums[i-1] {
continue
}
// Ранний выход: дальше только положительные
if nums[i] > 0 {
break
}
l, r := i+1, n-1
for l < r {
sum := nums[i] + nums[l] + nums[r]
switch {
case sum < 0:
l++
case sum > 0:
r--
default:
res = append(res, []int{nums[i], nums[l], nums[r]})
// Пропускаем дубликаты для l
lVal := nums[l]
for l < r && nums[l] == lVal {
l++
}
// Пропускаем дубликаты для r
rVal := nums[r]
for l < r && nums[r] == rVal {
r--
}
}
}
}
return res
}
func main() {
examples := [][]int{
{-1, 0, 1, 2, -1, -4},
{0, 0, 0, 0},
{-2, 0, 1, 1, 2},
}
for _, nums := range examples {
fmt.Println("Input:", nums)
fmt.Println("Triplets:", threeSum(append([]int{}, nums...)))
}
}