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

【题目】

　　给定排序数组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]
• 如果arr[left] + arr[right] > k，说明需要加一个更小的数，令right减1

计算的过程中要判断打印的元组之前是否打印过，只需要每次打印的时候检查 arr[left] 是否等于 arr[left-1]。整个时间复杂度O(N)。

下面是使用python3.5实现的代码。

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

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

def printUniqueTriad(arr, k):
    if arr == None or len(arr) <3:
        return
    for i in range(len(arr)):
        if i == 0 or arr[i] != arr[i-1]:
            left = i + 1
            right = len(arr) - 1
            while left <right:
                sum = arr[left] + arr[right]
                if sum == k - arr[i]:
                    if left == i+1 or arr[left] != arr[left-1]:
                        print(str(arr[i]) + "," + str(arr[left]) + "," + str(arr[right]))
                        left += 1
                        right -= 1
                elif sum > k - arr[i]:
                    right -= 1
                else:
                    left += 1