题解 | #三数之和#

#
# 
# @param num int整型一维数组 
# @return int整型二维数组
#
class Solution:
    def threeSum(self , num ):
        # write code here
        def twoSum(num, target, idx):
            lo, hi = idx, len(num)-1
            two_sum = []
            while lo < hi:
                if num[lo] + num[hi] == target:
                    two_sum.append([num[lo], num[hi]])
                    while lo + 1 < len(num) and num[lo] == num[lo+1]:
                        lo += 1
                    lo += 1
                    while hi - 1 >= 0  and num[hi] == num[hi-1]:
                        hi -= 1
                    hi -= 1
                elif num[lo] + num[hi] > target:
                    hi -= 1
                else:
                    lo += 1
            return two_sum
        if len(num) < 3:
            return []
        num.sort()
        res = []
        for i,n in enumerate(num):
            if n > 0:
                break
            if i-1 >= 0 and n == num[i-1]:
                continue
            temp = twoSum(num, -n, i+1)
            if temp:
                for t in temp:
                    res.append([n, t[0], t[1]])
        return res