Дан слайс целых чисел nums и число target. Найдите два разных элемента,
сумма которых равна target, и верните их индексы i < j. Если такой пары нет,
верните ok == false.
// TwoSum возвращает индексы i < j, для которых nums[i]+nums[j] == target.
// Если пары нет — ok == false (значения i, j тогда не важны).
func TwoSum(nums []int, target int) (i, j int, ok bool)
Требования
- Решение быстрее O(n²): квадратичный перебор не пройдёт тест на большом входе.
- Один и тот же элемент нельзя брать дважды:
TwoSum([]int{5}, 10) — пары нет.
- Если подходящих пар несколько, вернуть можно любую.
- Входной слайс не изменять.
Примеры
TwoSum([]int{4, 14, 22, 30}, 18) // 0, 1, true
TwoSum([]int{6, 4, 8}, 12) // 1, 2, true
TwoSum([]int{6, 6}, 12) // 0, 1, true
TwoSum([]int{4, 6, 10}, 12) // _, _, false
Ограничения: 0 <= len(nums) <= 10^6, значения и target по модулю не больше 10^9.
Устно: какая сложность по времени и памяти? Как найти все пары с суммой
target, если числа в массиве не повторяются ([4, 8, 10, 6], 14 → [[4, 10], [8, 6]])?