leetcode第15题 3Sum(三数之和)

我会带着你远行 2022-03-08 05:08 213阅读 0赞

比较简单的一道题，题目的大意是说：

> 给定一个长度为n的整数数组nums，从数组中找出所有不重复的 （三个数相加等于0的组合）。  
> 注意，仅字典序不同的、包含数字相同的三元组被认为是重复的，如（1，-1,0）和（0,1，,-1）被认为是重复的，只能保留其中一个。

样例输入：

> \[-1, 0, 1, 2, -1, -4\]

样例输出：

> \[  
> \[-1, 0, 1\],  
> \[-1, -1, 2\]  
> \]

输出不一定要和样例输出完全一样（组合的字典序问题），但必须包含所有可能的组合。

题目链接：[https://leetcode.com/problems/3sum/][https_leetcode.com_problems_3sum]

解题思路：

首先，最暴力的解法，直接三层循环，o(n^3)解决问题，这种方法很容易想到。时间复杂度太高了，我没交这种方法，不知道会不会超时。

怎么优化呢？可以用二分查找来做。

1.  先对数组进行排序，使用内置的排序方法，时间复杂度认为在O(nlogn)级别。
2.  既然是要找三个数的和为0的组合，那么，当前两个数确定了之后，第三个符合条件的数就确定了。这样，我们可以枚举前两个数，然后再在数组中使用二分查找搜索第三个数。时间复杂度可以认为在O(n^2logn)级别。  
    2.1 查找成功，则这三个数是一种满足条件的组合。  
    2.2 查找失败，则继续向下枚举。
3.  整体时间复杂度为O(nlogn+n2logn)=O((1+n2)logn)=O(n^2logn)。

样例代码（python3）：

# coding=utf-8
    
    class Solution:
    
        def bin_search(self, nums, key, left, right):
            """ 二分查找key是否在nums里面， 存在则返回任何一个值等于key的数组下标， 不存在则返回-1 :param nums: :param key: :param left: :param right: :return: """
            while left <= right:
                mid = (left + right) >> 1
                if key == nums[mid]:
                    return mid
                elif key < nums[mid]:
                    right = mid - 1
                else:
                    left = mid + 1
            return -1
    
        def threeSum(self, nums):
            """ :type nums: List[int] :rtype: List[List[int]] """
            length = len(nums)
            # 先排序，后面才能用二分查找
            nums = sorted(nums)
            # 所有符合条件的组合的结果集
            threesums = set()
            # 枚举前两个数
            for i in range(length - 2):
                if nums[i] > 0:
                    break
                for j in range(i + 1, length - 1):
                    tmp_sum = nums[i] + nums[j]
                    if tmp_sum > 0:
                        break
                    # 在数组中二分查找（0-tmp_sum）
                    pos = self.bin_search(nums, -tmp_sum, j + 1, length - 1)
                    if pos != -1:
                        # 找到了，就保存结果
                        threesums.add((nums[i], nums[j], nums[pos]))
            # 根据题目要求，以list的形式返回数据
            return list(threesums)

转载请注明出处：[https://blog.csdn.net/aaronjny/article/details/88550929][https_blog.csdn.net_aaronjny_article_details_88550929]

[https_leetcode.com_problems_3sum]: https://leetcode.com/problems/3sum/
[https_blog.csdn.net_aaronjny_article_details_88550929]: https://blog.csdn.net/aaronjny/article/details/88550929