本节学习寻找数组中三数之和为指定值所有集合的问题.该问题是采用左右双指针算法解决的典型问题之一,一三数之和为限制条件,适当调整左右指针.
问题描述:
给定一个包含n个整数的数组array,判断该数组是否存在三个元素x,y,z,是x+y+z等于0.
找出所有符合条件且不重复的三元组.
双指针算法思路解析:
仔细审阅题目,其实求x,y,z三数之和是否为0,可以视为求x和y两数之和是否等于-z.因此可以将数组先进行排序以避免不必要的遍历,降低复杂度;然后遍历整个数组一遍,可以将每个遍历到的元素视为-z在遍历过程中使用左右指针来分别指向当前元素的下一个元素及数组的最后一个元素.变量如下:
k变量:表示数组中的当前元素的位置
l变量:表示当前元素的下一个元素,其初始值为k+1
r变量:表示3个数中的第三个数字,其初始值为数组长度减一
res变量:表示最终返回的结果,包含所有和为0的不重复三元组
s变量:表示三数之和
代码如下:
array.sort()
res = []
for k in range(len(array) - 1)l,r = k+1,len(arry)-1只要左指针小于右指针,就继续通过不断计算三数之和决定左右指针是否应该移动,并且在移动过程中不断跳过重复元素.判断过程分为三种,当三数之和为0时,需要再判断res数组中是否已存在此三元数组,如果不存在,则添加到res中;让后继续让左指针向右移动,右指针向左移动,在移动过程中再使用一个循环不断跳过重复元素,以提高代码效率
当三数之和小于0时,说明其中的元素需要增大.由于数组已经是排序后的,因此让左指针向右移动可以使三数之和增大,当三数之和大于0时同理
整体代码如下:
def threeSum(self, arry):# 对数组进行排序arry.sort()# 初始化结果列表res = []# 遍历数组，k代表当前考虑的第一个数for k in range(len(arry)-2):# 如果当前数大于0，则后面的数之和一定大于0，可以提前结束循环if arry[k] > 0: break# 跳过重复的元素，避免找到重复的三元组if k > 0 and arry[k] == arry[k-1]: continue# 初始化左右指针l, r = k+1, len(arry)-1# 使用双指针查找和为0的三元组while l < r:s = arry[k] + arry[l] + arry[r]# 如果三数之和小于0，移动左指针if s < 0:l += 1# 跳过重复的元素while l < r and arry[l] == arry[l-1]: l += 1# 如果三数之和大于0，移动右指针elif s > 0:r -= 1# 跳过重复的元素while l < r and arry[r] == arry[r-1]: r -= 1# 如果三数之和等于0，找到了一个解else:# 将三元组添加到结果列表中res.append((arry[k], arry[l], arry[r]))# 移动左右指针，寻找下一个解l += 1r -= 1# 跳过重复的元素while l < r and arry[l] == arry[l-1]: l += 1while l < r and arry[r] == arry[r+1]: r -= 1# 返回所有找到的三元组return res
