【python程序员代码面试指南】不重复打印排序数组中相加和为给

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

打印结果为：   1, 9  和 2, 8 

  [要求] 时间复杂度为O(n)O(n)O(n)，空间复杂度为O(1)O(1)O(1)

分析：第一种复杂度较高的方法，可以采用遍历一遍数组，然后采用二分的方法进行查找。第二种方法，则是通过首尾指针进行搜索。

【1】code：

def binary_chop(lists, data):

    begin = 0

    end = len(lists) - 1

    while begin <= end:

        mid = (begin + end) // 2

        if lists[mid] > data:

            end = mid - 1

        elif lists[mid] < data:

            begin = mid + 1

        else:

            return mid

    return False

arr = [-8, -4, -3, 0, 1, 2, 4, 5, 8, 9]

k = 10

lis = []

for i in range(len(arr)):

    m = k - arr[i]

    j = binary_chop(arr, m)

    if j != False and i != j and j not in lis:

        print(arr[i], arr[j])

        lis.append(i)

【2】code

[n, k] = [10, 10]#[n,k] = list(map(int,input().split()))

lists = [-8, -4, -3, 0, 1, 2, 4, 5, 8, 9]#lists = list(map(int,input().split()))

start = 0

end = len(lists) - 1

while start < end:

    if lists[start] + lists[end] == k:

        print(lists[start],lists[end])

        j = start

        while ((start < end) and (lists[j] == lists[start])):

            start += 1

        j = end

        while ((start < end) and (lists[j] == lists[end])):

            end -= 1

    elif lists[start] + lists[end] < k:

        start += 1

    else:

        end -= 1

程序的运行结果为：

1， 9

2， 8