LeetCode06：三数之和

6.三数之和

题目

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请

你返回所有和为 0 且不重复的三元组。

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

题解

（一）暴力解法（三重循环）

使用三层嵌套循环来枚举所有可能的三个数的组合。

时间复杂度：对于每个元素a，它都与后面所有可能的b和c元素进行了比较。为O($n^3$)，n是数组的长度。

空间复杂度：由于 arr 可能包含大量的三元组，所以这部分的空间复杂度是最高的，为 O($n^3$)。

class Solution:
    def compareArr(self,arr):
        unique_str = []
        res = []
        for x in arr:
            new_str = ''.join(map(str,sorted(x)))
            if new_str not in unique_str:
                unique_str.append(new_str)
                res.append(x)
        return res
    def threeSum(self, nums):
        arr = []
        count = 0
        for i,a in enumerate(nums[:-2]):
            for b in nums[i+1:-1]:
                for c in nums[i+2+count:]:
                    if a+b+c == 0:
                        arr.append([a,b,c])
                count = count + 1
            count = 0


        res = self.compareArr(arr)
        return res

（二）双指针法

1、排序。先将 nums 排序，时间复杂度为 O(NlogN)。

2、特判。非数组返回空；数组首元素大于0返回空（因为后面的肯定比它大，和不可能为0）；数组长度小于3返回空；

3、设置指针。固定最左（最小）元素的指针a ，再使用左右指针指向a后面元素的两端，分别为l,r。

4、循环条件。

• 左指针索引j要小于右指针索引k；

• 如果a大于0，则条件一定不能满足，结束循环；

• 如果a和前一个数字相等，说明数字重复，会导致结果重复，跳过；

5、求和。

• 如果和等于0，添加到结果列表。左指针右移，右指针左移。在此之前，都需要判断是否下一个元素重复，如果重复就跳过，因为会导致结果重复；
• 如果和大于0，右指针左移；
• 如果和小于0，左指针右移。（左右移动不需要考虑下一个元素重复，因为我们是在调整指针尝试可能的三元组，不需要担心重复。

class Solution:
    def threeSum(self,nums):
        nums = sorted(nums)
        length = len(nums)
        res = []
        if not nums or nums[0]>0 or length<3:
            return []
        for i,a in enumerate(nums[:-2]):
            if a>0:
                return res
            if i>0 and nums[i-1] == a:
                continue
            j = i + 1
            k = length - 1
            while(j<k):
                l = nums[j]
                r = nums[k]
                total = a+l+r
                if total == 0:
                   res.append([a,l,r])
                   while j < k and nums[k-1] == nums[k]:
                      k -= 1
                   while j<k and nums[j+1]==nums[j]:
                      j += 1
                   k-=1
                   j+=1
                elif total >=0:
                    k -= 1
                elif total <= 0:
                    j += 1
        return res

图解