题解 | #数组中相加和为0的三元组#

'''
解题思路：
首先排序；
第一个数字i遍历整个数组从0~len-2，若num[i]>0提前退出
然后定义双指针j,k一前一后，判断三个值的和与0的大小关系，
若等于0，j前移，k后移，判断无重复加入结束数组
若小于0，j前移，
若大于0，k后移
'''
# @param num int整型一维数组 
# @return int整型二维数组
#
class Solution:
    def threeSum(self , num ):
        # write code here
        n = len(num)
        if n<3:
            return []

        num = sorted(num)
        #print('num=',num)
        res = []
        for i in range(n-2):
            if num[i]>0:
                break
            j = i+1
            k = n-1            
            while j<k:
                if num[i]+num[j]+num[k]==0:
                    t = [num[i],num[j],num[k]]
                    if t not in res:
                        res.append(t)
                    j += 1
                    k -= 1
                elif num[i]+num[j]+num[k]<0:
                    j += 1
                elif num[i]+num[j]+num[k]>0:
                    k -= 1  
        #print('res=',res)
        return res

Solution().threeSum([-10,0,0,0,0,10,10,10,20,-10,-10,10,-10,-40]) # [[-10, -10, 20], [-10, 0, 10], [0, 0, 0]]