Дан массив чисел nums и целевое число target. Найдите все уникальные комбинации из четырех чисел в nums, которые суммируются в target.
Решение "Two Pointers"
package main
import (
"fmt"
"sort"
)
func fourSum(nums []int, target int) [][]int {
sort.Ints(nums) // Сортируем исходный слайс
return kSum(nums, target, 4, 0) // Вызываем функцию kSum для поиска всех комбинаций, дающих заданный результат
}
func kSum(nums []int, target int, k int, index int) [][]int {
var res [][]int // Создаем двумерный слайс, в который будут сохранятся все комбинации, дающие заданный результат
if index >= len(nums) { // Если индекс выходит за пределы слайса, то возвращаем пустой слайс
return res
}
if k == 2 { // Если k равно 2, то используем алгоритм двух указателей для поиска пары чисел, дающих заданный результат
left, right := index, len(nums)-1
for left < right { // Пока левый указатель меньше правого...
sum := nums[left] + nums[right] // ...считаем сумму элементов, указанных левым и правым указателями
if sum == target { // Если сумма равна заданному результату...
res = append(res, []int{nums[left], nums[right]}) // ...добавляем найденную комбинацию в ответ...
for left < right && nums[left] == nums[left+1] { // ...пропуская одинаковые элементы слева...
left++
}
for left < right && nums[right] == nums[right-1] { // ...и одинаковые элементы справа
right--
}
left++ // Передвигаем левый указатель вправо
right-- // Передвигаем правый указатель влево
} else if sum < target { // Если сумма меньше заданного результата...
left++ // ...передвигаем левый указатель вправо
} else { // Если сумма больше заданного результата...
right-- // ...передвигаем правый указатель влево
}
}
} else { // Если k не равно 2...
l := len(nums) - k + 1 // ...вычисляем длину слайса для текущего k
for i := index; i < l; i++ { // Перебираем все возможные индексы для текущего k
if i > index && nums[i] == nums[i-1] { // Если элемент слайса уже был использован в предыдущей итерации, то пропускаем его
continue
}
sub := kSum(nums, target-nums[i], k-1, i+1) // Рекурсивно вызываем функцию kSum для поиска всех комбинаций, дающих заданный результат для текущего k-1 и начиная с индекса i+1
for j := 0; j < len(sub); j++ { // Добавляем текущий элемент слайса ко всем комбинациям, дающим заданный результат для текущего k-1
res = append(res, append([]int{nums[i]}, sub[j]...))
}
}
}
return res // Возвращаем все найденные комбинации, дающие заданный результат
}
func main() {
var nums []int
// Input: nums = [1,0,-1,0,-2,2], target = 0
// Output: [[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]
nums = []int{1, 0, -1, 0, -2, 2}
fmt.Printf("%v\n", fourSum(nums, 0))
// Input: nums = [2,2,2,2,2], target = 8
// Output: [[2,2,2,2]]
nums = []int{2, 2, 2, 2, 2}
fmt.Printf("%v\n", fourSum(nums, 8))
}Это решение использует рекурсивный подход для решения задачи kSum, который затем используется для решения задачи fourSum. Сначала мы сортируем массив nums, чтобы упростить поиск комбинаций. Затем мы вызываем kSum с k = 4 и index = 0, чтобы найти все уникальные комбинации из четырех чисел, которые суммируются в target. Если k == 2, мы используем два указателя, чтобы найти все уникальные пары чисел, которые суммируются в target. Если k > 2, мы рекурсивно вызываем kSum с k - 1 и index = i + 1, чтобы найти все уникальные комбинации из k - 1 чисел, которые суммируются в target - nums[i]. Затем мы добавляем nums[i] к каждой комбинации и добавляем её в результат.
Алгоритмическая сложность функции fourSum() зависит от сложности алгоритма kSum(), который она вызывает. В данном случае, для каждого k от 2 до 4, функция kSum() рекурсивно вызывается на слайсе длиной (n-k+1), где n - длина исходного слайса. В худшем случае, когда k=4, сложность будет O(n^3), так как kSum() вызывается 4 раза, каждый раз на слайсе, длиной (n-k+1), что дает нам O((n-3)(n-2)(n-1)) = O(n^3).
Решение "Hash Set"
package main
import (
"fmt"
"sort"
)
func fourSum(nums []int, target int) [][]int {
// Сортировка входного массива
sort.Ints(nums)
// Создание мапы для хранения уникальных комбинаций
m := make(map[[4]int]bool)
// Создание слайса для хранения результирующих комбинаций
var res [][]int
// Получение длины массива
ln := len(nums)
// Перебор всех возможных комбинаций из 4 чисел
for i := 0; i < ln-3; i++ {
// Оптимизация: Пропуск повторяющихся значений на первой позиции
// if i > 0 && nums[i] == nums[i-1] {
// continue
// }
for j := i + 1; j < ln-2; j++ {
// Оптимизация: Пропуск повторяющихся значений на второй позиции
// if j > i+1 && nums[j] == nums[j-1] {
// continue
// }
// Использование двух указателей для перебора оставшихся чисел
l, r := j+1, ln-1
for l < r {
sum := nums[i] + nums[j] + nums[l] + nums[r]
if sum == target {
// Добавление уникальной комбинации в мапу и в слайс результатов
a := [4]int{nums[i], nums[j], nums[l], nums[r]}
if !m[a] {
m[a] = true
res = append(res, a[:])
}
// Оптимизация: Пропуск повторяющихся значений на третьей и четвертой позиции
// for l < r && nums[l] == nums[l+1] {
// l++
// }
// for l < r && nums[r] == nums[r-1] {
// r--
// }
// Инкремент левого указателя и декремент правого, чтобы двигаться к центру
l++
r--
} else if sum < target {
// Если сумма меньше целевого значения, двигаем левый указатель вправо
l++
} else {
// Если сумма больше целевого значения, двигаем правый указатель влево
r--
}
}
}
}
// Возвращаем слайс с уникальными комбинациями чисел, дающими сумму target
return res
}
func main() {
var nums []int
// Input: nums = [1,0,-1,0,-2,2], target = 0
// Output: [[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]
nums = []int{1, 0, -1, 0, -2, 2}
fmt.Printf("%v\n", fourSum(nums, 0))
// Input: nums = [2,2,2,2,2], target = 8
// Output: [[2,2,2,2]]
nums = []int{2, 2, 2, 2, 2}
fmt.Printf("%v\n", fourSum(nums, 8))
}Алгоритмическая сложность функции fourSum() составляет O(n^3), так как функция содержит 3 вложенных цикла, каждый из которых проходит от 0 до n элементов, где n - длина входного массива nums.