[LeetCode][Python]15. 三数之和

[LeetCode][Python]15. 三数之和

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

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

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

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

解题思路：

1. 暴力枚举？
2. 还是没有思路
   参考别人：
   先将给定nums排序，简化问题，复杂度为O(nlogn)。

令nums[k] + nums[i] + nums[j] == 0，找所有的组合的思路是：遍历三个数字中最左数字的指针k，找到数组中所有不重复k对应所有b c组合，即每指向新的nums[k]，都通过双指针法找到所有和为0的nums[i] nums[j]并记录：

当nums[k] > 0时，直接跳出，因为j > i > k，所有数字大于0，以后不可能找到组合了；

当k > 0 and nums[k] == nums[k - 1]，跳过此数字，因为nums[k - 1]的所有组合已经被加入到结果，如果本次搜索，只会搜索到重复组合。

i, j分设在[k, len(nums)]两端，根据sum与0的大小关系交替向中间逼近，如果遇到等于0的组合则加入res中，需要注意：移动i j需要跳过所有重复值，否则重复答案会被计入res。

先排序再查找nlogn快排，第一层循环从起点位置开始枚举a，从剩余数组中查找b和c。因为先排序了，所以b和c可以向中间靠拢。如果a+b+c>0，则c从最右端向左移动一位。如果a+b+c<0，则b从最左端向右移动一位。看是否等于0的情况。因为b和c都是线性的往中间移动的，所以时间复杂度是O(N^2)。但是就地查找，没有新开辟set空间，所以空间复杂度是O(1)。

    def threeSum2(self, nums):
        res = []
        nums.sort()
        for i in range(len(nums) - 2):
            if i > 0 and nums[i] == nums[i-1]:
                continue
            l, r = i+1, len(nums) - 1
            while l < r:
                s = nums[i] + nums[l] + nums[r]
                if s < 0:
                    l += 1 # 左边界向右移动一步
                elif s > 0:
                    r -= 1 # 右边界向左移动一步
                else:
                    res.append([nums[i], nums[l], nums[r]])
                    # 过滤重复的结果
                    while l < r and nums[l] == nums[l+1]:
                        l+=1
                    while l < r and nums[r-1] == nums[r]:
                        r -= 1
                    l += 1
                    r -= 1
        return res