题解 | #三数之和#

花了好长时间思考算法，主要思想就是尽可能通过条件判断来减少循环的次数。将所有的数进行分类，大于0，小于0，和等于0一共三类，存到数组内并按照从小到大排列。 条件判断依据子数组的结构，不含有0（两正一负，两负一正）；含有1个0（那么肯定是一正一负，判断小于0的数的相反数在不在大于0长度数组内），以及含有3个0（那么就是[0,0,0]）。 当然，这个程序有很多的bug，在不含有0的情况下，len(z_list)会报错，另外，可以设置条件减少搜寻的次数，例如两正一负的情况，如果两个正数之和开始大于负数最大的绝对值时，没有必要搜索了，因为这个是按照从小到大排列的，后面不会有跟它相反的负数。

# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param num int整型一维数组 
# @return int整型二维数组
#
class Solution:
    def threeSum(self , num: List[int]) -> List[List[int]]:
        # write code here
        pd = []
        s_list = [i for i in num if i<0]
        s_list.sort(reverse=False)#小于0的数组并排序
        b_list = [i for i in num if i>0]
        b_list.sort(reverse=False)#大于0的数组并排序
        z_list = [i for i in num if i==0] #等于0的数组
        

        #a+b+c=0 一定有一正一负，所以从分别的数组里循环，可以减少循环次数
        #如果这个数组里面有0
        if len(s_list) !=0 and len(b_list) !=0:
            #不使用0，两正1负 或者两负一正
            if len(z_list)!=0:
                for i in s_list:
                    if ((-i) in b_list) and [i,0,-i] not in pd:
                        pd.append([i,0,-i])  #使用1个0
                        
            if len(s_list)>=2:
                for i in range(0,len(s_list)):
                    for j in range(i+1,len(s_list)):
                        if -(s_list[i]+s_list[j]) in b_list and [s_list[i],s_list[j],-(s_list[i]+s_list[j])] not in pd:
                            pd.append([s_list[i],s_list[j],-(s_list[i]+s_list[j])])
            if len(b_list)>=2:
                for i in range(0,len(b_list)):
                    for j in range(i+1,len(b_list)):
                        if -(b_list[i]+b_list[j]) in s_list and [-(b_list[i]+b_list[j]),b_list[i],b_list[j]] not in pd:
                            pd.append([-(b_list[i]+b_list[j]),b_list[i],b_list[j]])
        if len(z_list) >=3:
            pd.append([0,0,0]) #使用3个0
        
        pd.sort(reverse = False)
        return pd