题目：给定排序数组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
网友评论