题目
给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？找出所有满足条件且不重复的三元组。
注意：答案中不可以包含重复的三元组。
例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4]，
满足要求的三元组集合为：
[
[-1, 0, 1],
[-1, -1, 2]
]
解答
方案1：暴力求解
定义结果列表，用左、中、右三个指针寻找所有可能的三数组合，逐一辨别是否和为0，把满足条件的组合放在结果列表中。
这里需要注意的是，答案中不可以包含重复的三元组，例如[-1,0,1]和[0,1,-1]不能都保留，为了不把出现过的组合也添加到结果中，我们增加了一个新的结果列表，用于存储排序后的结果，根据当前组合排序后是否出现在这个列表中，来决定是否将当前组合加入结果列表。
class Solution1:
def threeSum(self, nums):
res = [] # 结果列表
sorted_res = [] # 结果列表,用于添加排序后的记录，便于去重
for right in range(2, len(nums)):
for middle in range(1, right):
for left in range(middle):
cur_cmb = [nums[left], nums[middle], nums[right]] # 当前组合
sorted_cmb = sorted(cur_cmb) # 对当前组合进行排序
if sum(cur_cmb) == 0 and sorted_cmb not in sorted_res: # 确保当前组合在结果中没有出现过
res.append(cur_cmb)
sorted_res.append(sorted_cmb)
return res
不过还是超时了。。
方案2：固定中间，移动两头
结果进行排序，然后根据有序数组的特点进行遍历；
让左指针（left）从数组左侧第一个数开始向右遍历，每当左指针移动到一个位置时，固定左指针，中指针（middle）和右指针（right）初始状态分别位于左指针右侧和数组最右端；
判断当前三数之和与0的大小，如果比0大，说明右指针对应的数字偏大，应该向左移动一个单位，反之将中指针向右移动一个单位（这里移动一个单位指的的找到下一个不一样的数）；
如果中指针和右指针相遇，则进入下一轮循环，将左指针移动到下一个位置；
遍历过程中记录当前符合要求的组合。
这里有一个要求，就是不能出现重复的组合，因此指针在滑动时，如果下一个字符和当前字符相同，我们要继续滑动，知道找到和当前字符不一样的字符位置，这里我们用一个函数“slide2next_diff”实现这一功能。
class Solution:
def threeSum(self, nums):
def slide2next_diff(nums, cur_idx, limit, direction='right'):
"""
# 滑动到下一个与当前数字不相同的数字，返回其位置
:param nums: 输入整个数组
:param cur_idx: 指针当前所在的位置
:param limit: 指针移动时的最远位置，注意：不会到达，只能相邻
:param direction: 移动方向，left或right
:return: 下一个与当前字符不同的字符所在的位置下标
"""
if direction == 'right': # 如果方向向右
limit = min(limit, len(nums))
cur_idx += 1
while nums[cur_idx] == nums[cur_idx-1] and cur_idx < limit: # 只要相等，继续右移
cur_idx += 1
elif direction == 'left': # 如果方向向左
limit = max(limit, 0)
cur_idx -= 1
while nums[cur_idx] == nums[cur_idx+1] and cur_idx > limit: # 只要相等，继续左移
cur_idx -= 1
else:
raise Exception('请输入正确的滑动方向，left或right。')
return cur_idx
nums.sort() # 首先将输入列表排序
res = [] # 结果列表
left = 0 # 左指针开始位置
while 0 <= left <= len(nums) - 2: # 左指针从第一个数开始向右遍历，到倒数第三个结束
middle, right = left + 1, len(nums)-1 # 初始化中指针和右指针位置，分别为左指针后一个数和整个数组最后一个数
while middle < right: # 下标满足条件时
cur_cmb = [nums[left], nums[middle], nums[right]] # 当前组合
cur_sum = sum(cur_cmb) # 当前组合的和
if cur_sum == 0: # 满足条件，添加到结果列表
res.append(cur_cmb)
# 中指针向右，右指针向左移动到下一个和本位置不同的数
middle = slide2next_diff(nums, cur_idx=middle, limit=right, direction='right')
right = slide2next_diff(nums, cur_idx=right, limit=middle, direction='left')
elif cur_sum > 0: # 和大于零，右指针左移
right -= 1
else: # 和小于零，左指针右移
middle += 1
# 左指针向右移动到和当前不同的数
left = slide2next_diff(nums, cur_idx=left, limit=len(nums)-1, direction='right')
return res
如有疑问或建议，欢迎评论区留言~
