LeetCode-3Sum

问题:

Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != ji != 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
  • -105 <= nums[i] <= 105

 

解答:

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

  • 对于下一个数据和当前数据相同, 跳过
if nums[i] == nums[i-1] and i > 0: 
  continue
  • 2 如果三数之和为0 , 那么要过滤掉相邻相同的数据
while left < right and nums[left] == nums[left +1]: 
  left += 1 
while left < right and nums[right] == nums[right-1]: 
  right -=1

 

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

参考及引用

https://leetcode.com/problems/3sum/discuss/7392/Python-easy-to-understand-solution-(O(n*n)-time).

Photo by Lucas Pezeta from Pexels

Comments are closed.