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

题目

　　给定排序数组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:
        return

    left = 0
    right = len(arr) - 1

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

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

def printUniqueTried(arr,k):

    if arr == None or len(arr) < 3:
        return

    for i in range(len(arr)):

        left = i + 1
        right = len(arr) - 1
        sum_  = arr[left] + arr[right]

        if sum_-arr[i] > k:
            right -= 1
        elif sum_-arr[i] < k:
            left += 1
        else:
            if left == i+1 or arr[left-1]!=arr[left]:
                print(str(arr[i])+','+ str(arr[left])+','+str(arr[right]))
                left +=1
                right -=1