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

#
# 
# @param num int整型一维数组 
# @return int整型二维数组
#
# 分析：三个数字相加为0，情况无外乎如下三种：
#     1.数字中本身就有三个0
#     2.数组中有一个0，另外两个数字互为相反数
#     3.三个数字总和为0
#     但是从上述情况出发思考找这样三个数字，似乎不太方便
#     之前我们做过类似的题目，但是题目中是找两个数的和为某一个值的数，此处用0减去第一个数，作为
#     输入，就可以把该问题转化为求两数之和的问题，首先进行排序并借由双指针方法，完成本题的计算
#     排序之后，当所取的第一个值i>=0 时，后边就不会出现满足条件的数了，故可以停止
class Solution:
    def threeSum(self , num ):
        # write code here
        num.sort()
        if num == [] or num[0] > 0:
            return []
        i = 0
        pre = 0
        le = len(num)
        ans = []
        #由于要取三个数字，所以i最大取到倒数第三个就可以，防止越界
        while i < le - 2 and num[i] < 0:
            if num[i] == pre and i < le:
                i += 1
            else:
                target = -num[i]
                j = i + 1    # j 不能等于i，所以也要+1
                k = le - 1   # 这里k的值应为le-1 别忘了
                while j < k:
                    if num[j] + num[k] > target:
                        k -= 1
                    elif num[j] + num[k] < target:
                        j += 1
                    else:
                        ans.append([num[i],num[j],num[k]]) 
                        while j+1 < k and num[j] == num[j+1]:
                            j += 1
                        while j < k-1 and num[k] == num[k-1]:
                            k -= 1
                        k -= 1   #满足情况之后，也需要对指针进行操作
                        j += 1   #否则会出现死循环
                pre = num[i] #由于存在 -1 -1 2 这种可能，所以说要在数组存在的时候，再排除首项相同的情况
                i += 1
        #分析中提到的三个数字都是0的情况，需要额外注意
        if num[i] == 0  and i+2<le and num[i+1] ==0 and num[i+2] == 0:
            ans.append([0,0,0])
        return ans