目录

AaronJny

诗酒繁华,书剑天涯。

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

比较简单的一道题,题目的大意是说:

给定一个长度为 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/

解题思路:

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

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

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


标题:leetcode第15题 3Sum(三数之和)
作者:AaronJny
地址:https://aaronjny.com/articles/2019/11/06/1573017427765.html