15、三数の和(python)

9086 ワード

タイトル:
n個の整数を含む配列numsを与えて、numsの中に3つの要素a,b,cが存在するかどうかを判断して、a+b+c=0にしますか?条件を満たし、繰り返さないすべての三元グループを見つけてください.
注意:答えに重複する三元グループは含まれてはいけません.
例:
     nums = [-1, 0, 1, 2, -1, -4],

           :
[
  [-1, 0, 1],
  [-1, -1, 2]
]

コード(ソート+ダブルポインタ):
class Solution:
    def threeSum(self, nums):
        if len(nums) < 3:                 #       < 3,     
            return []
        nums = sorted(nums)               #   
        re = []                           #     
        for i in range(len(nums)):                  #   
            if nums[i] > 0:                         #   nums[i] > 0,        0,    re
                return re 
            if i > 0 and nums[i] == nums[i-1]:      #       
                continue
            L = i + 1                               #    
            R = len(nums) - 1                       #    
            while L < R:                                      #   
                temp = nums[i] + nums[L] + nums[R]            #     
                if temp == 0:                                 #  temp = 0
                    re.append([nums[i],nums[L],nums[R]])      #         
                    while L < R and nums[L] == nums[L+1]:     #             ,  
                        L = L + 1
                    while L < R and nums[R] == nums[R-1]:     #             ,  
                        R = R - 1
                    L = L + 1                       #      ,  
                    R = R - 1                       #      ,  
                elif temp > 0:                                #  temp > 0
                    R = R - 1                                 #            ,      
                else:                                         
                    L = L + 1                                 #   ,          ,      
        return re