LintCode 57. 三数之和 Python算法

描述

给出一个有n个整数的数组S，在S中找到三个整数a, b, c，找到所有使得a + b + c = 0的三元组。

说明

在三元组(a, b, c)，要求a <= b <= c。

结果不能包含重复的三元组。

样例

- 例1:

输入:[2,7,11,15]
输出:[]

- 例2:

输入:[-1,0,1,2,-1,-4]
输出:[[-1, 0, 1],[-1, -1, 2]]

解析

class Solution:
    def threeSum(self, nums):
        if not nums or len(nums) < 3:
            return []
        result = []
        for i in range(len(nums)-2):
            target = - nums[i]
            dict = {}
            for j in range(i+1,len(nums)):
                if target-nums[j] in dict:
                    res = sorted([nums[i],nums[j],target-nums[j]])
                    if res not in result:
                        result.append(res)
                else:
                    dict[nums[j]] = j
        return result

运行结果