15-3Sum

100-Same Tree | Links:

题意

Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero. 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: []

思路

• 数学题： sum
• 3sum转换为2sum + 双指针Sliding Window
• 遇到重复值跳过

class Solution(object):
    def threeSum(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        res = []
        
        # check range
        if not nums or len(nums) <3: return res
        # sort
        nums = sorted(nums)
        # 3sum转换为2sum:遍历中固定一个值
        # 双指针找另外两个值
        for i in range(len(nums)-2):
            # 第一个数重复跳过
            if (i > 0) and nums[i] == nums[i-1]: continue
            left,right = i+1,len(nums)-1
            while left < right:
                target = 0-nums[i]
                if nums[left] + nums[right] == target:
                    res.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 nums[left] + nums[right] < target:
                    left += 1
                else : 
                    right -= 1
        return res

分析:

• Time: O(n^2)
• Space: O(n)