python三数之和

116 阅读 0 评论 77 点赞

我是靠谱客的博主舒适手链，这篇文章主要介绍python三数之和，现在分享给大家，希望可以做个参考。

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

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

示例 1：

输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
示例 2：

输入：nums = []
输出：[]
示例 3：

输入：nums = [0]
输出：[]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/3sum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

根据题目，我们只需要判断两个条件：

三数之和是否为0
三数各不相同

第一个我相信都可以做到，重点是第二个，怎么判断三数各不相同。我们来看看怎么去实现的

复制代码

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
def threeSum(nums: list[int]):
    li = []
    if len(nums) < 3:  # 列表长度小于3就直接返回
        return
    nums.sort()
    n = len(nums)
    for i in range(n):
        if nums[0] > 0:  # 因为我们已经将列表排序过，所以如果排序后的列表第一个元素还是大于0的，那么肯定没有三个数相加为0
            return li
        if i > 0 and nums[i] == nums[i - 1]:  # 判断连续的两个元素是否相同，相同则跳过一个
            continue
        l = i + 1
        r = n - 1
        while l < r:
            if nums[i] + nums[l] + nums[r] == 0:
                li.append([nums[i], nums[l], nums[r]])
                while l < r and nums[l] == nums[l + 1]:
                    l += 1
                while l < r and nums[r] == nums[r - 1]:
                    r -= 1
                l += 1
                r -= 1
            elif nums[i] + nums[l] + nums[r] > 0:
                r -= 1
            else:
                l += 1
    return li

从代码我们可以看出，我们先将列表排序，然后遍历列表，然后定义左指针和右指针分别指向第二个元素和最后一个元素。之后循环判断三数相加是否为0，如果存在满足的三个数，则不断的判断左右指针两旁的元素是否相同，如果有相同的，那么左右指针朝相应的方向移动。如果三数之和大于0，那么代表右指针靠右，往左移动即可（因为我们的列表是排序的，大于零就是数大了）。反之左指针相应移动。