数组中和为0的三个数

题目描述:
给定一个包含 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]
输出：[]

提示：
0 <= nums.length <= 3000
-105 <= nums[i] <= 105

解答思路:
如果一上来就3个循环暴力破解, 时间复杂度就为O(n3), 需要换个思路, 不妨先排个序, 将[-1,0,1,2,-1,-4] 变成 [-4, -1, -1, 0, 1, 2], 接下来, 先固定第一个数 -4, 然后在
[-1, -1, 0, 1, 2]这个列表中进行双指针遍历, 这个类似于我之前写的 排序数组中2个数字之和的3中解法

def double_point(nums):
    # 对列表进行升序排序
    nums.sort()
    result_list = list()
    for n, i in enumerate(nums):
        # 如果大于0了, 后续加起来肯定不会等于0
        if i > 0:
            break
        # 如果和上一个数一样, 那就没必要重复了
        if n > 0 and i == nums[n - 1]:
            continue
        # 对列表进行切片
        nums2 = nums[n + 1:]
        # 如果切片后的列表长度等于2,说明已经是最后3个了
        if len(nums2) == 2:
            if sum(nums[n:]) == 0:
                result_list.append(nums[n:])
            break
        # 开始双指针查找
        low, high = (0, len(nums2) - 1)
        while low < high:
            if i + nums2[low] + nums2[high] == 0:
                result_list.append([i, nums2[low], nums2[high]])
                while True:
                    # try是为了防止报错
                    try:
                        # 如果下一个也是一样的数,那就不必要重复了
                        if nums2[low] == nums2[low + 1]:
                            low += 1
                        else:
                            break
                    except:
                        break
                # 下一个不是一样的数, 那就把左边的指针往右边移动
                low += 1
            # 如果3个数加起来小于0, 则把指针往右移动
            elif i + nums2[low] + nums2[high] < 0:
                low += 1
            else:
                high -= 1
    return result_list

最后在力扣上面跑的分数如下, 速度比官方解答还快几十ms

如果对您有帮助, 麻烦您点个赞, 如果有问题或不同的想法欢迎交流, 一起进步

最后

以上就是俊逸河马为你收集整理的数组中和为0的三个数的全部内容，希望文章能够帮你解决数组中和为0的三个数所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。