不重复打印排序数组中相加和为给定值的所有二元组和三元组

题目

　　给定排序数组arr和整数k，不重复打印arr中所有相加和为k的不降序二元组。例如，arr = [-8, -4, -3, 0, 1, 2, 4, 5, 8, 9]，k = 10，打印结果为：1,9　2,8

补充题目

　　给定排序数组arr和整数k，不重复打印arr中所有相加和为k的不降序三元组。例如，arr = [-8, -4, -3, 0, 1, 2, 4, 5, 8, 9]，k = 10，打印结果为： -4, 5, 9 　-3, 4, 9　 -3, 5, 8　 0, 1, 9　 0, 2, 8　 1, 4, 5

基本思路

　　利用排序后数组的特点，可以设置两个指针left和right，left从左边开始移动，right从右边开始移动。初始时 left = 0，right = len(arr) - 1。之后比较 arr[left] + arr[right] 和 k ，情况如下：

如果arr[left] + arr[right] == k，满足条件，将这个两个元素打印出来
如果arr[left] + arr[right] < k，说明需要加一个更大的数，令left加1
如果arr[left] + arr[right] > k，说明需要加一个更小的数，令right减1
计算的过程中要判断打印的元组之前是否打印过，只需要每次打印的时候检查 arr[left] 是否等于 arr[left-1]。整个时间复杂度O(N)。

def printUniquePair(arr,k):if arr == None or len(arr) < 2:returnleft = 0right = len(arr) - 1while left < right:if arr[left] + arr[right] < k:left +=1elif arr[left] + arr[right] > k:right -=1else:if left == 0 or arr[left-1] != arr[left]:print(str(arr[left-1]) + ',' + str(arr[left]))left +=1right-=1

打印三元组的方法类似。只需要提前确定第一个元素（假设为a），剩下的两个元素只需要按照打印二元组的方法找累加和为 k - a 的二元组。为了不重复打印，在确定第一个元素的时候也要判断是否之前出现过。实现代码如下：

def printUniqueTried(arr,k):if arr == None or len(arr) < 3:returnfor i in range(len(arr)):left = i + 1right = len(arr) - 1sum_ = arr[left] + arr[right]if sum_-arr[i] > k:right -= 1elif sum_-arr[i] < k:left += 1else:if left == i+1 or arr[left-1]!=arr[left]:print(str(arr[i])+','+ str(arr[left])+','+str(arr[right]))left +=1right -=1

 

《新程序员》：云原生和全面数字化实践50位技术专家共同创作，文字、视频、音频交互阅读

总结

以上是生活随笔为你收集整理的不重复打印排序数组中相加和为给定值的所有二元组和三元组的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。