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

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

热度指数：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

备注:

算法知识视频讲解

椰汁giao

#include<bits/stdc++.h>
using namespace std;
int main(){
    long n,k,a[100005];
    scanf("%ld%ld",&n,&k);
    for(int i=0;i<n;i++){
        scanf("%ld",&a[i]);
    }
    for(int i=0,j=n-1;i<j;){
        int x=a[i]+a[j];
        if(x==k){
            printf("%ld %ld\n",a[i++],a[j--]);
            while(a[i]==a[i-1])i++;
            while(a[j]==a[j+1])j--;
        }else if(x>k){
            j--;
        }else{
            i++;
        }
    }
}

发表于 2022-03-12 17:28:28 回复(0)