每日一道算法之--三数之和

双指针哈希表排序

Word count: 748Reading time: 3 min

 2020/02/24   Share

三数之和

力扣第15题：https://leetcode-cn.com/problems/3sum/
给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？找出所有满足条件且不重复的三元组。

注意：答案中不可以包含重复的三元组。

示例：

给定数组 nums = [-1, 0, 1, 2, -1, -4]，
满足要求的三元组集合为：
[
[-1, 0, 1],
[-1, -1, 2]
]

1. 排序 + 双指针解法

题目中的要求是不能含有相同的三元组，所以在算法中我们需要去重，排序是一个很好的方法，因为排序可以让相同的数连载一起，方便判断去重。让后在通过双指针对数组一一检查，找到所有合适的三元组。

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        # 先将nums排序
        nums.sort()
        res = []
        for i in range(len(nums) - 2):
            # 设置两个指针
            l, r = i + 1, len(nums) - 1
            if nums[i] > 0 : return res
            # 去除重复的判断,因为nums[i -1]已经包含了nums[i]的所有组合的可能性
            if i > 0 and nums[i] == nums[i - 1] : continue
            while l < r:
                s = nums[i] + nums[l] + nums[r]
                if s < 0:
                    # 如果和小于0，证明左边的数太小了，需要往后移
                    l += 1
                    # 去除重复的判断，但是前提条件为l<r
                    while l < r and nums[l] == nums[l - 1]: l += 1
                elif s > 0:
                    r -= 1
                    # 如果和大于0，证明右边的数太大了，需要往前移
                    while l < r and nums[r] == nums[r + 1]: r -= 1
                else:
                    res.append([nums[i], nums[l], nums[r]])
                    l += 1
                    r -= 1
                    while l < r and nums[l] == nums[l - 1]: l += 1
                    while l < r and nums[r] == nums[r + 1]: r -= 1
        return res

1.1 时间复杂度分析

时间复杂度：排序的时间复杂度为 O(NlogN), 遍历数组为O(N),双指针的遍历为O(N),所以总的时间复杂度为$$O(NlogN)+0(N)*O(N) = O(N^2)$$

空间复杂度：没有用到额外的数据结构，所以空间复杂度为$$O(1)$$

2.哈希索引的方法（空间换时间）

参考两数之和，我们可以构建哈希表的方法使查找效率变得更高。

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        if len(nums) < 3:
            return []
        nums.sort()
        # 因为a+b = 0等价于a = -b
        target_hash = {-x: i for i, x in enumerate(nums)}
        res = []
        res_hash = {}
        # 从零开始检索,到倒数第二位结束
        for i, first in enumerate(nums[:-1]):
            if nums[i] > 0: return res
            if i > 0 and first == nums[i - 1]:
                continue
            #从第一个指针的下一位开始搜索 
            for j, second in enumerate(nums[i + 1:]):
                # 检查两数之和是否存在于哈希表target_hash中
                if first + second in target_hash:
                    target_index = target_hash[first + second]
                    if target_index == i or target_index == i + j + 1:
                        continue
                    # 将找到的结果存入另一个哈希表中, 避免包含重复结果
                    row = sorted([first, second, nums[target_index]])
                    key = ",".join([str(x) for x in row])
                    if key not in res_hash:
                        res.append(row)
                        res_hash[key] = True
        return res

Author：liangweijiang

原文链接：https://liangweijiang.github.io/2020/02/24/algorithm-15/

发表日期：February 24th 2020, 5:25:51 pm

更新日期：March 2nd 2020, 6:30:37 pm

Next Post

DRF源码解析5--认证组件的封装和初始化
Previous Post

DRF源码解析4--版本控制组件的封装

CATALOG

1. 三数之和
1. 1.1. 1. 排序 + 双指针解法
  1. 1.1.1. 1.1 时间复杂度分析
2. 1.2. 2.哈希索引的方法（空间换时间）

