#15 3Sum——Top 100 Liked Questions

- 日理万妓 2022-02-03 02:34 137阅读 0赞

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.

**Note:**

The solution set must not contain duplicate triplets.

**Example:**

Given array nums = [-1, 0, 1, 2, -1, -4],
    
    A solution set is:
    [
      [-1, 0, 1],
      [-1, -1, 2]
    ]

> """
> 
> 第一次：暴力解法，三层嵌套循环，时间超时，但本地运行正确
> 
> """
> 
>     class Solution(object):
>         def threeSum(self, nums):
>             """
>             :type nums: List[int]
>             :rtype: List[List[int]]
>             """
>             length = len(nums)
>             result = []
>             for i in range(0, length):
>                 for j in range(i + 1, length):
>                     if -(nums[i] + nums[j]) in nums[j+1:]:
>                         if sorted([nums[i], nums[j], -(nums[i] + nums[j])]) not in result:
>                             result.append(sorted([nums[i], nums[j], -(nums[i] + nums[j])]))
>             return result
> 
> """
> 
> Time Limit Exceeded
> 
> """

>  """
> 
> 第二次：参考网上思路，先对数组排序，采用两个指针辅助，只需遍历两次。设置首尾两个指针ij，求p与ij的和，如果sum>0，其中一值需要减小，此时p是固定的，所以j前移一位，若sum<0，其中一值需要增大，i后移一位，若sum=0，将pij保存下来。但是时间超时。
> 
> 应该对特殊的情况进行考虑：1）对于相同的两个p，只查找一个就可以，避免了重复；2）当找到一组pij时，如果i+1与i的值是相同时，为了避免重复，i继续想后寻找下一个不同的值；3）同2）的思想
> 
> """
> 
>     class Solution(object):
>         def threeSum(self, nums):
>             """
>             :type nums: List[int]
>             :rtype: List[List[int]]
>             """
>             result = []
>             nums = sorted(nums)
>             for p in range(0, len(nums) - 2):
>                 if p > 0 and nums[p - 1] == nums[p]:                         #1）
>                     continue
>                 i, j = p + 1, len(nums) - 1
>                 while i < j:
>                     sums = nums[p] + nums[i] + nums[j]
>                     if sums > 0:
>                         j -= 1
>                     elif sums < 0:
>                         i += 1
>                     else:
>                         result.append(sorted([nums[p], nums[i], nums[j]]))
>                         while i < j and nums[i] == nums[i + 1]:              #2）
>                             i += 1
>                         while i < j and nums[j] == nums[j - 1]:              #3）
>                             j -= 1
>                         j -= 1
>                         i += 1
>             return result
> 
> """
> 
> Runtime: 660 ms, faster than 76.34% of Python online submissions for3Sum.
> 
> Memory Usage: 15.6 MB, less than 20.42% of Python online submissions for 3Sum.
> 
> """

> """
> 
> 第三次：又加了一个判断条件，4）因为nums是从小到大排列的，如果某个p大于零了，那么后面的也不用看了，因为三个正数的和不可能为0
> 
> """ 
> 
>     class Solution(object):
>         def threeSum(self, nums):
>             """
>             :type nums: List[int]
>             :rtype: List[List[int]]
>             """
>             result = []
>             nums = sorted(nums)
>             for p in range(0, len(nums) - 2):
>                 if nums[p] > 0:                                           #4）
>                     break
>                 if p > 0 and nums[p - 1] == nums[p]:                      #1）
>                     continue
>                 i, j = p + 1, len(nums) - 1
>                 while i < j:
>                     sums = nums[p] + nums[i] + nums[j]
>                     if sums > 0:
>                         j -= 1
>                     elif sums < 0:
>                         i += 1
>                     else:
>                         result.append(sorted([nums[p], nums[i], nums[j]]))
>                         while i < j and nums[i] == nums[i + 1]:          #2）
>                             i += 1
>                         while i < j and nums[j] == nums[j - 1]:          #3）
>                             j -= 1
>                         j -= 1
>                         i += 1
>             return result
> 
> """
> 
> Runtime: 560 ms, faster than 90.46% of Python online submissions for3Sum.
> 
> Memory Usage: 15.5 MB, less than 20.42% of Python online submissions for 3Sum.
> 
> """