算法题：牛牛的三元组问题

牛牛的三元组问题_牛客题霸_牛客网

描述

动物牛牛是一个勇敢的冒险家，它正在探索一个神秘的岛屿。岛上有许多宝藏，但是宝藏被隐藏在一系列数字中。牛牛找到了一个整数数组 nums，它相信这个数组中存在一些特殊的三元组，满足以下条件：

• 三元组的和等于 0。
• 三元组中的元素不能重复。
• 牛牛想按照字典序返回所有满足条件的三元组。

请你帮助牛牛解决这个问题，设计一个函数 findTriplets，接收一个整数数组 nums 作为参数，并返回一个二维整数数组，表示满足条件的三元组，按照字典序返回所有的三元组。

示例1

输入：

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

复制返回值：

[[-1,-1,2],[-1,0,1]]

复制

示例2

输入：

[2, -1, 1, -2, 0, -2]

复制返回值：

[[-2,0,2],[-1,0,1]]

复制

备注：

• 3 <= nums.length <= 3000
• 数组中的整数范围为 [-10^5, 10^5]

解题思路：先排序，然后直接3个for循环，但在具体操作过程中，需要去除重复三元组，所以加了两处判断：

if i > 0 and nums[i] == nums[i - 1]:

if j > i + 1 and nums[j] == nums[j - 1]:

算法完整代码：# 31ms, 6392KB

class Solution:
    def findTriplets(self, nums):
        # [-2, -2, -1, 0, 1, 2]
        nums = sorted(nums)
        n = len(nums)
        ans_set = []
        for i in range(n - 2):
            if i > 0 and nums[i] == nums[i - 1]:
                continue
            if nums[i] > 0:
                break
            j = i + 1
            while j < n - 1:
                if j > i + 1 and nums[j] == nums[j - 1]:
                    j += 1
                    continue
                if (nums[i] + nums[j]) > 0:
                    break
                for k in range(j + 1, n):
                    if nums[i] + nums[j] + nums[k] > 0:
                        break
                    elif nums[i] + nums[j] + nums[k] == 0:
                        ans_set.append([nums[i], nums[j], nums[k]])
                        break
                j += 1

        return ans_set


if __name__ == '__main__':
    sol = Solution()
    # print(sol.findTriplets([-1, 0, 1, 2, -1, -4]))
    # print(sol.findTriplets([2, -1, 1, -2, 0, -2]))
    print(sol.findTriplets([0, 0, 0, 0, 0, 0]))