🔍Тестовое собеседование с Go TeamLead из американского FinTech в этот четверг

23 октября(в четверг!) в 19:00 по мск приходи онлайн на открытое собеседование, чтобы посмотреть на настоящее интервью на Middle Go-разработчика.

Как это будет:
📂 Дмитрий Дорофеев, Go TeamLead в американском FitTech Truv Inc, ex-VK, будет задавать реальные вопросы и задачи разработчику-добровольцу
📂 Дмитрий будет комментировать каждый ответ респондента, чтобы дать понять, чего от вас ожидает собеседующий на интервью
📂 В конце можно будет задать любой вопрос Дмитрию

Это бесплатно. Эфир проходит в рамках менторской программы от ШОРТКАТ для Go-разработчиков, которые хотят повысить свой грейд, ЗП и прокачать скиллы.

Переходи в нашего бота, чтобы получить ссылку на эфир → @shortcut_go_bot

Реклама.
О рекламодателе.

👣 Задача дня: 3Sum

Вам дан массив целых чисел 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...)))
  }
}