LeetCode-3Sum

Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.

Notice that the solution set must not contain duplicate triplets.

Example 1:

Input:

 nums = [-1,0,1,2,-1,-4]

Output:

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

Example 2:

Input:

 nums = []

Output:

 []

Example 3:

Input:

 nums = [0]

Output:

 []

Constraints:

• 0 <= nums.length <= 3000
• -10⁵ <= nums[i] <= 10⁵

解答:

与Two Sum不同这个题目中存在相同的数据， 处理思路是先考虑数据不重复， 将list升序排序后，遍历每个元素的同时判断其存在两个值使其满足三数之和为0， 两个值分别取大于当前值的最小值和最大值由于数组是排序的，如果三数之和大于0，那么减小最大值索引， 如果三数之和小于0，增加最小值索引。

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        if len(nums) <= 1:
            return []
        nums.sort()
        tripleset = []
        pre = 0
        for i in range(len(nums)): 
            if nums[i] == nums[i-1] and i > 0: 
                continue
            left = i + 1
            right = len(nums) - 1
            while left < right:            
                sum = nums[i] + nums[left] + nums[right]
                if sum == 0 :
                    tripleset.append([nums[i] ,nums[left], nums[right]])
                    while left < right  and nums[left] == nums[left +1]:
                        left += 1
                    while left < right  and nums[right] == nums[right-1]:
                        right -=1
                    left += 1
                    right -= 1
                elif sum < 0:
                    left += 1
                elif sum > 0:
                    right -= 1
                    
                      
        return tripleset