LeetCode中的题2

比眉伴天荒 2022-03-19 08:23 186阅读 0赞

给定一个包含 *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(object):
        def threeSum(self, nums):
            """
            :type nums: List[int]
            :rtype: List[List[int]]
            """
            list = []
            for i in range(len(nums)):
                for j in range(len(nums)):
                    if i == j:
                        continue
                    for k in range(len(nums)):  
                        if k == j or k == i :
                            continue
                        
                        if [nums[i], nums[j], nums[k]] in list or [nums[j], nums[i], nums[k]] in list or [nums[k], nums[j], nums[i]] in list or [nums[k], nums[i] ,nums[j]] in list or [nums[i], nums[k], nums[j]] in list or [nums[j], nums[k], nums[i]] in list :
                            continue
                        if nums[i] + nums[j] + nums[k] == 0:
                            list.append([nums[i], nums[j] ,nums[k]])
            return list

虽然能解出答案，但是超时

评论中更好的解题方案

class Solution(object):
        def threeSum(self, nums):
            """
            :type nums: List[int]
            :rtype: List[List[int]]
            """
            nums.sort()
            res =[]
            i = 0
            for i in range(len(nums)):
                if i == 0 or nums[i]>nums[i-1]:
                    l = i+1
                    r = len(nums)-1
                    while l < r:
                        s = nums[i] + nums[l] +nums[r]
                        if s ==0:
                            res.append([nums[i],nums[l],nums[r]])
                            l +=1
                            r -=1
                            # 同一位置的数不能想等
                            while l < r and nums[l] == nums[l-1]:
                                l += 1
                            while r > l and nums[r] == nums[r+1]:
                                r -= 1
                        elif s>0:
                            r -=1
                        else :
                            l +=1
            return res

耗时744ms,先排序，将三数之和变为两数之和，在循环去重使用二分法

感觉思维还是有点僵