15. 三数之和
15. 三数之和
给定一个包含 n 个整数的数组nums，判断nums中是否存在三个元素 a，b，c ，使得a + b + c = 0 ？找出所有满足条件且不重复的三元组。
注意：答案中不可以包含重复的三元组。
例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4]，
满足要求的三元组集合为：
[
[-1, 0, 1],
[-1, -1, 2]
]
class Solution:
def threeSum(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
num_dict = self.list2dict(nums)
num_negative = num_dict['num_negative']
num_positive = num_dict['num_positive']
num_results = []
for i in range(len(num_negative)):
for j in range(len(num_positive)):
list_result = []
list_result.append(num_negative[i])
list_result.append(num_positive[j])
sum = num_negative[i] + num_positive[j]
sum = -sum
if sum<0:
if sum < num_negative[i]:
break
else:
if sum < num_positive[j]:
continue
if num_negative[i] == num_positive[j] == 0:
if num_dict[num_negative[i]]>=3:
list_result.append(0)
elif sum in num_dict:
if sum == num_negative[i] or sum == num_positive[j]:
if num_dict[sum]>1:
list_result.append(sum)
else:
continue
else:
list_result.append(sum)
if len(list_result) == 3:
num_results.append(list_result)
return num_results
def list2dict(self, nums):
'''
数组转换成字典
:param nums:
:return:
'''
num_dict = {}
num_positive = []
num_negative = []
for i in range(len(nums)):
if nums[i] in num_dict:
num_dict[nums[i]]+=1
else:
num_dict[nums[i]]=1
if nums[i]<=0:
num_negative.append(nums[i])
if nums[i]>=0:
num_positive .append(nums[i])
num_dict['num_positive'] = self.paixu(num_positive)
num_dict['num_negative'] = self.paixu(num_negative)
return num_dict
def paixu(self, nums):
for i in range(len(nums)):
for j in range(len(nums)-i-1):
if nums[j] >nums[j+1]:
n = nums[j]
nums[j] = nums[j+1]
nums[j+1] = n
y=1
while y < len(nums): #去重
if nums[y] == nums[y-1]:
nums.pop(y)
continue
else:
y+=1
return nums
