Python

Задача на python

Имеется массив целых чисел numbers. Необходимо найти все такие тройки [numbers[i], numbers[j], numbers[k]], где i != j, j != k, k != i и сумма numbers[i] + numbers[j] + numbers[k] = 0
Пример: nums = [4,-1,7,0,1,2,-1,5], тройки: [[-1,-1,2],[-1,0,1]]
 from itertools import combinations 

nums = [4,-1,7,0,1,2,-1,5]
res1 = (tuple(sorted(x)) for x in combinations(nums, 3) if sum(x) == 0)
res2 = list(map(list, set(res1)))
print(res)
т.к. в списке есть одинаковые элементы, то чтобы убрать результаты, отличающиеся лишь порядком элементов пришлось столько фильтров применить, ну и преобразовать результат к списку списков как в примере
Екатерина Козырева
Екатерина Козырева
25 445
Лучший ответ
Dior Khalikov Кубическая сложность, избыточная. Вон даже нейросеть в предыдущем ответе квадратичный алгоритм нашла.
Александр Колесов Айран, могли бы Вы подробнее описать каждую строчку кода?
Вы можете использовать технику двух указателей для решения этой задачи. Вначале, отсортируйте массив чисел. Затем, итерируйте по каждому числу. Для каждого числа, установите один указатель справа от текущего числа и другой указатель в самом конце массива. Далее, смещайте указатели в зависимости от суммы трех чисел. Если сумма меньше нуля, смещайте левый указатель вправо. Если сумма больше нуля, смещайте правый указатель влево. Если сумма равна нулю, добавьте эти три числа в результирующий список и смещайте оба указателя.

Вот пример кода:

```python
def threeSum(nums):
res = []
nums.sort()
for i in range(len(nums)-2):
if i > 0 and nums[i] == nums[i-1]:
continue
l, r = i+1, len(nums)-1
while l < r:
s = nums[i] + nums[l] + nums[r]
if s < 0:
l += 1
elif s > 0:
r -= 1
else:
res.append([nums[i], nums[l], nums[r]])
while l < r and nums[l] == nums[l+1]:
l += 1
while l < r and nums[r] == nums[r-1]:
r -= 1
l += 1; r -= 1
return res

nums = [4,-1,7,0,1,2,-1,5]
print(threeSum(nums))
```

Этот код сначала сортирует массив `nums`, затем ищет тройки чисел, сумма которых равна нулю. Если такие тройки найдены, они добавляются в список `res`, который затем возвращается функцией. Результатом этого кода будет `[[[-1, -1, 2], [-1, 0, 1]]`.
Рубен Григорян
Рубен Григорян
14 606
Dior Khalikov Интересно, автор сможет угадать отступы? Хотя, неважно, т.к. код всё равно не работает.
Dior Khalikov Хотя, нет, на данном примере работает, просто я отступы не сразу угадал. Оставлю их в тайне, так интереснее. :-)