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

[编程题]不重复打印排序数组中相加和为给定值的所有二元组

热度指数：15327 时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定排序数组arr和整数k，不重复打印arr中所有相加和为k的不降序二元组

例如, arr = [-8, -4, -3, 0, 1, 2, 4, 5, 8, 9], k = 10，打印结果为：

1, 9

2, 8

[要求]

时间复杂度为

，空间复杂度为

输入描述:

第一行有两个整数n, k
接下来一行有n个整数表示数组内的元素

输出描述:

输出若干行，每行两个整数表示答案
按二元组从小到大的顺序输出(二元组大小比较方式为每个依次比较二元组内每个数)

示例1

输入

10 10
-8 -4 -3 0 1 2 4 5 8 9

输出

1 9
2 8

备注:

算法知识视频讲解

Python

fighting@SHU

if __name__=='__main__':
    
    aa=list(map(int,input().split()))
    bb=list(map(int,input().split()))
    bb=list(set(bb))
    bb=sorted(bb)
    i=0
    j=len(bb)-1
    target=1
    while i<j:
        if (bb[i]+bb[j])<aa[1]:
            i+=1
        elif (bb[i]+bb[j])==aa[1]:
            print(bb[i],bb[j])
            i+=1
            j-=1
        else:
            j-=1

有个疑问，为什么这个通过率为60%，思想也是双指针的

发表于 2019-08-25 19:08:24 回复(2)

Python

牛妹儿子

n, k = map(int, input().split())
nums = list(map(int, input().split()))
left = 0
right = len(nums) - 1
while left < right:
    if nums[left] + nums[right] == k:
        print(nums[left], nums[right])
        num_left = nums[left]
        while left < right and nums[left] == num_left:
            left += 1
        num_right = nums[right]
        while left < right and nums[right] == num_right:
            right -= 1
    elif nums[left] + nums[right] < k:
        left += 1
    else:
        right -= 1
# 注意中间有相同的数字，需要处理，不然就重复打印了

编辑于 2019-08-04 18:51:20 回复(0)