Имеется массив целых чисел 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]]
Python
Задача на python
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)
т.к. в списке есть одинаковые элементы, то чтобы убрать результаты, отличающиеся лишь порядком элементов пришлось столько фильтров применить, ну и преобразовать результат к списку списков как в примере
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]]`.
Вот пример кода:
```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]]`.
Dior Khalikov
Интересно, автор сможет угадать отступы? Хотя, неважно, т.к. код всё равно не работает.
Dior Khalikov
Хотя, нет, на данном примере работает, просто я отступы не сразу угадал. Оставлю их в тайне, так интереснее. :-)
Похожие вопросы
- Решение задач по python
- Нужно решить задачу на Python
- Помогите решить задачу на Python. Никак не могу решить задачу, больше дня не могу найти ответ! Никакой код не работает.
- Python# Можно помощь с задачей на Python
- Еще одна задача в Python
- Пожалуйста, помогите решить задачу на Python. Упражнения 57,58,59,60.
- Интересная задача на PYTHON?
- Задача на Python
- Пожалуйста, помогите решить задачу на Python. Упражнение 124, 125, 146
- Помогите пожалуйста с задачей на Python.