a + b + c = 0 且不重复的三元组

微信公众号：三木小小推^[1]
系列：刷题之Python
如果你觉得该系列对你有帮助，欢迎点好看^[2]

问题描述

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

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

例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4]，

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

解决方案

 class Solution:
    def threeSum(self, nums):
        nums.sort()
        len_nums = len(nums)
        index_left = 0
        results = []
        index_right = len_nums - 1

        while index_left < (index_right - 1):

            in_index_mid = index_left + 1
            in_index_right = index_right

            if nums[index_left] + nums[index_right - 1] + nums[index_right] < 0:
                index_left += 1
                continue

            if nums[index_left] + nums[index_left + 1] + nums[index_right] > 0:
                index_right -= 1
                continue

            while in_index_mid < in_index_right:

                sum_nums = nums[index_left] + nums[in_index_mid] + nums[in_index_right]

                if (sum_nums) == 0 and [nums[index_left], nums[in_index_mid],
                                        nums[in_index_right]] not in results:

                    results.append([nums[index_left], nums[in_index_mid],
                                    nums[in_index_right]])
                    in_index_mid += 1
                elif sum_nums < 0:
                    in_index_mid += 1
                elif sum_nums > 0:
                    in_index_right -= 1

                else:
                    in_index_mid += 1


            index_left += 1


        return results

测试

nums = [-4,-2,-2,-2,0,1,2,2,2,3,3,4,4,6,6]
sol = Solution()
print(sol.threeSum(nums))

[[-4, -2, 6], [-4, 0, 4], [-4, 1, 3], [-4, 2, 2], [-2, -2, 4], [-2, 0, 2]]

题目分析

排序后
三指针查找
夹逼原则

欢迎订阅

下面是三木小小推的二维码，欢迎订阅呦~~

你点的每个好看，我都认真当成了喜欢