[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]]
解题思路：
- 暴力枚举？
- 还是没有思路
参考别人：
先将给定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
