LeetCode 15. 三数之和（中）

双指针经典题目，用二分查找解决将three sum转换成two sum的问题再解决。

题目

给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？找出所有满足条件且不重复的三元组。

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

示例

示例： 

1
2
3
4
5
6
7
给定数组 nums = [-1, 0, 1, 2, -1, -4]，

满足要求的三元组集合为：
[
  [-1, 0, 1],
  [-1, -1, 2]
]

考察知识点

排序、双指针、数组

核心思想

方法一

先排序，后用双指针解决将three sum转换成two sum的问题。

先对数组进行排序，然后使用双指针进行处理，排序之后可以帮助排除一些情况。 算法流程 1、特判，对于数组长度 n，如果数组为 null 或者数组长度小于 3，返回 [][]。 2、对数组进行排序。 3、遍历排序后数组：
- 若 nums[i]>0：因为已经排序好，所以后面不可能有三个数加和等于 0，直接返回结果。
- 对于重复元素：跳过，避免出现重复解 - 令左指针L=i+1，右指针 R=n-1，当L<R时，执行循环： - 当 nums[i]+nums[L]+nums[R]==0，执行循环，判断左界和右界是否和下一位置重复，去除重复解。并同时将 L,R移到下一位置，寻找新的解 - 因为整体左小右大，所以若和大于 0，说明 nums[R] 太大，R 左移， nums[R] 减小。 - 同上，若和小于 0，说明 nums[L] 太小，L 右移， nums[L] 增大。

做这个题目的关键，是要把握规律，有时候，提前排序，可以减少很多可能性，提升性能。

定义三个指针，i，j，k。遍历i，那么这个问题就可以转化为在i之后的数组中寻找nums[j]+nums[k]=-nums[i]，这个问题，也就将三数之和问题转变为二数之和。（可以使用双指针）

方法二

先排序，然后用二分查找解决将three sum转换成two sum的问题

Python版本

先排序后双指针

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
class Solution:
    def threeSum(self, nums: list) -> list:
        
        _len = len(nums)
        res=[]
        if(not nums or _len<3):
            return []
        nums.sort()
        for i in range(_len):
            if(nums[i]>0):  # 因为已经排序好，所以后面不可能有三个数加和等于 0，直接返回结果。
                return res
            if(i>0 and nums[i]==nums[i-1]):  # 注意这里是i-1 如果和前面的一样，也就是出现重复元素 直接跳过
                continue
            L = i + 1  # 左指针
            R = _len - 1  # 右指针
            while(L<R):
                if(nums[i]+nums[L]+nums[R]==0):
                    res.append([nums[i],nums[L],nums[R]])  # 当nums[i]+nums[L]+nums[R]==0时，执行循环，判断左界和右界是否和下一位置重复，去除重复解。并同时将 L,R移到下一位置，寻找新的解。
                    while(L<R and nums[L]==nums[L+1]):  # 去除重复解
                        L = L + 1
                    while(L<R and nums[R]==nums[R-1]):  # 去除重复解  注意右指针去重复是R = R -1
                        R = R - 1
                    L = L + 1
                    R = R - 1
                elif(nums[i]+nums[L]+nums[R]>0):  # 因为整体左小右大，所以若和大于 0，说明 nums[R] 太大。R 左移， nums[R]减小。
                    R=R-1
                else:  # 若和小于 0，说明 nums[L] 太小，L 右移， nums[L] 增大。
                    L=L+1
        return res


print("leet code accept!!!")
Input = [[-1, 0, 1, 2, -1, -4]]
Answer = [
    [
        [-1, 0, 1], 
        [-1, -1, 2]
    ]
]


if __name__ == "__main__":
    solution = Solution()
    for i in range(len(Input)):
        print("-"*50)
        result = solution.threeSum(Input[i])
        print(result)
        print(Answer[i])

一个基于bisect实现二分查找的方法

前期的预处理很重要，构建了输入字符和出现次数的关系。减少不必要的计算。预处理和二分查找使得这个算法的运行速度在前98.18%。但是，可读性太差了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
import bisect
class Solution:
    def threeSum(self, nums: list) -> list:
        ans = []
        counts = {}
        for i in nums:
            # Input nums: [-1, 0, 1, 2, -1, -4]
            # counts: {-4: 1, -1: 2, 0: 1, 1: 1, 2: 1}
            counts[i] = counts.get(i, 0) + 1  # 构建一个以输入nums的value为key、输入nums的出现次数为value的dict。

        nums = sorted(counts)  # 对counts的key进行排序，到这里的预处理，一方面记录了nums的每个值出现的次数，一方面还在去重的基础上进行了排序，当输入数据较多时，这种先去重并记录并发值，后排序的方法就能赢得性能优势

        for i, num in enumerate(nums):
            if counts[num] > 1:  # 先判断该数字出现次数是否大于1
                if num == 0 and counts[num] > 2:  # 若该数字为0且出现次数大于2时，可以得到一个[0, 0, 0]的答案
                    ans.append([0, 0, 0])
                elif -num * 2 in counts:  # 由于counts[num] > 1 则该数字至少出现2次，判断0-2*num是否存在，如果存在，则可以得到一个[num, num, -2*num]的答案
                    ans.append([num, num, -2 * num])

            # 使用bisect.bisect_left和bisect.bisect_right就可以实现二分查找，bisect不会真的插入，但是会返回插入值的位置。
            if num < 0:  # 再判断该数字是否小于0 只有小于0 才能用于将three sum转化成two sum
                two_sum = -num  # 转化为两数之和问题 two_sum为要求解的和
                # bisect.bisect_left(a, x, lo=0, hi=len(a)) 查找在有序列表 a 中插入 x 的index。lo 和 hi 用于指定列表的区间，默认是使用整个列表。如果 x 已经存在，在其左边插入。返回插入位置。
                # 由于nums是有序的，所以nums[-1]为nums最大的数，two_sum - nums[-1]为剩下需要的数值，找不到就默认返回i + 1
                left = bisect.bisect_left(nums, (two_sum - nums[-1]), i + 1)
                # bisect.bisect_right(a, x, lo=0, hi=len(a)) 类似于 bisect_left()，但是返回的插入点是 a 中已存在元素 x 的右侧。
                # bisect.bisect_right(nums, (two_sum // 2), left) 会返回一个往nums中插入two_sum // 2时的插入点，默认是left
                # 从nums[left: 返回值]子list中寻找满足 j + i = two_sum 且 j在counts中 且 j != i  以此构造新的答案
                for i in nums[left: bisect.bisect_right(nums, (two_sum // 2), left)]:
                    j = two_sum - i
                    if j in counts and j != i:
                        ans.append([num, i, j])

        return ans

执行用时 :432 ms, 在所有 Python3 提交中击败了98.18%的用户
内存消耗 :33 MB, 在所有 Python3 提交中击败了5.01%的用户