首页 > 试题广场 >

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

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

热度指数：15186 时间限制：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

备注:

算法知识视频讲解

C/C++

nbgao

#include <bits/stdc++.h>
using namespace std;

int main(){
    int n, k;
    cin>>n>>k;
    int a[n];
    for(int i=0;i<n;i++)
        cin>>a[i];
    int l=0, r=n-1;
    while(l<r){
        if(a[l]+a[r]==k){
            if(l==0 || a[l]!=a[l-1])
                cout<<a[l]<<" "<<a[r]<<endl;
            l++;
            r--;
        }else if(a[l]+a[r]<k)
            l++;
        else
            r--;
    }
    return 0;
}

编辑于 2020-07-04 19:01:46 回复(8)

Java

Mono_Chrome

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        int[] arr = new int[n];

        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }

        int i = 0;
        int j = n - 1;
        while (i < j) {
            int sum = arr[i] + arr[j];
            if (sum < k) {
                i++;
            } else if (sum > k) {
                j--;
            } else {
                if (i == 0 || arr[i] != arr[i - 1] || j == n - 1) {
                    System.out.println(arr[i] + " " + arr[j]);
                }
                i++;
                j--;
            }
        }
    }
}

发表于 2019-10-10 16:34:28 回复(1)

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)

无心2019

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n,k;
    cin>>n>>k;
    vector<int>num(n);
    for(int i=0;i<n;i++)
        cin>>num[i];
    int i=0,j=n-1;
    while(i<j)
    {
        if(num[i]+num[j]<k)
            i++;
        else if(num[i]+num[j]>k)
            j--;
        else
        {
            if(i==0||num[i]!=num[i-1]||j==n-1)
                cout<<num[i]<<" "<<num[j]<<endl;
            i++;
            j--;
        }
    }
    return 0;
}

发表于 2019-08-23 20:56:02 回复(3)

圣诞节的安徒生

不重复打印确实是要注意的，可能有好多个（1 9）组合，但是我们只输出一次

#接收用户输入的两个整数
n,k = map(int,input().split())
#将n个整数存放到列表中
ls = list(map(int,input().split()))
#先排个序，不用排序，因为是有序数组
#ls.sort() 
#i,j赋初值，从首尾开始向中间遍历
i, j = 0, n-1
while i < j:
    if ls[i]+ls[j] < k: #小于k,i向后
        i += 1
    elif ls[i]+ls[j] == k: #当存在一个形如（1 9）的组合时，跳过1之后的1和9之前的9
        print(ls[i], ls[j])
        while ls[i]==ls[i+1]:
            i += 1
        while ls[j] == ls[j-1]:
            j -= 1
        #有重复则跳过，同时i,j向中间收缩
        i += 1
        j -= 1
    else: #大于k,j向前
        j -= 1

编辑于 2019-08-13 23:15:13 回复(0)

pein531

由于是已经排序好的数组，因此可以使用双指针法来保证O(n)的时间复杂度，注意在移动指针的时候需要去重

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] params = br.readLine().split(" ");
        int n = Integer.parseInt(params[0]), k = Integer.parseInt(params[1]);
        String[] strArr = br.readLine().split(" ");
        int[] arr = new int[n];
        for(int i = 0; i < n; i++) arr[i] = Integer.parseInt(strArr[i]);
        int left = 0, right = n - 1;
        while(left < right) {
            if(arr[left] + arr[right] < k){
                left ++;
            }else if(arr[left] + arr[right] > k){
                right --;
            }else{
                if(left == 0 || arr[left] != arr[left - 1])
                    System.out.println(arr[left] + " " + arr[right]);
                left ++;
                right --;
            }
        }
    }
}

发表于 2021-06-28 23:01:47 回复(0)

巨白龙

前后双标志向中间靠近，和大于k向前走，小于向后走

发表于 2019-08-20 09:11:58 回复(0)

C/C++

但求八月九月好运！

//这一题只要清楚不能出现重复的就可以，直接用map更方便一些
#include<iostream>
#include<vector>
#include<map>
using namespace std;
int main(){
    int n,k;
    cin>>n>>k;
    vector<int>data(n);
    for(int i=0;i<n;++i)
        cin>>data[i];
    map<int,int>res;
    auto p=data.begin();
    auto q=data.end()-1;
    while(p!=q){
        if(*p+*q==k){
            if(res.find(*p)==res.end())
                res[*p]=*q;
            ++p;
            if(p==q) break;
            else --q;
        }
        else if(*p+*q<k)
            ++p;
        else
            --q;
    }
    for(auto ptr=res.begin();ptr!=res.end();++ptr)
        cout<<ptr->first<<" "<<ptr->second<<endl;
    return 0;
}

编辑于 2019-08-10 20:23:13 回复(2)

Python 3

今年还能有offer吗

为什么测试用例过不了，提交却能成功？

n , t = map(int,input().split())

arr = list(map(int,input().split()))
arr = list(set(arr))
arr.sort()
r = len(arr) - 1
l = 0
while l <= r :
if arr[l] + arr[r] < t:
l += 1
elif arr[l] + arr[r] > t:
r -= 1
elif arr[l] + arr[r] == t:
print(arr[l],arr[r])
l += 1
r -= 1

发表于 2022-06-16 12:04:06 回复(0)

Java

牛客135290605号

第6个示例没过，求大佬指点
import java.util.*;
public class Main{
    public static void main(String[]args){
        Scanner scanner=new Scanner(System.in);
        int n=scanner.nextInt();
        int k=scanner.nextInt();
        
        HashSet<Integer>set=new HashSet<Integer>();
        int arr[]=new int[n];
        for(int i=0;i<n;i++){
            arr[i]=scanner.nextInt();
            set.add(arr[i]);
        }
        
        for(int i=0;i<n-1;i++){
            int temp=k-arr[i];
            if(set.contains(temp)&arr[i]<temp){
                System.out.println(arr[i]+" "+temp);
                set.remove(temp);
            }
        }
    }   
}

发表于 2022-06-07 21:24:13 回复(0)

牛客235394036号

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int K = sc.nextInt();
        int []arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }
        printByOrder(K, arr);
    }

    private static void printByOrder(int k, int[] arr) {
        int i = 0;
        int j =arr.length - 1;
        while(i < j){
            if (arr[i] + arr[j] < k) i++;
            else if(arr[i] + arr[j] > k) j--;
            else {
                if (i == 0|| arr[i] != arr[i -1]){
                    System.out.print(arr[i]);
                    System.out.print(" ");
                    System.out.println(arr[j]);
                }
                i++;
                j--;
            }
        }
    }
}

发表于 2022-05-25 14:17:14 回复(0)

Python 3

牛客989469880号

n,k=map(eval,input().split())
arr=list(map(eval,input().split()))
re=set()
left=0
right=n-1
while left<right:
if arr[left]+arr[right]>k:
right-=1
elif arr[left]+arr[right]<k:
left+=1
elif arr[left]+arr[right]==k:
if (arr[left],arr[right]) not in re:
print(arr[left],arr[right])
re.add((arr[left],arr[right]))
left+=1

right-=1

一定要考虑重复值的问题

发表于 2022-04-10 12:08:32 回复(0)

椰汁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)

牛客66319561号

#include<iostream>
#include<vector>
#include<set>
using namespace std;

int main()
{
    int n,k;
    cin>>n>>k;
    vector<int> matrix(n,0);
    for(int i=0;i<n;++i){
        cin>>matrix[i];
    }
    int i=0,j=n-1;
    while(i<j){
  
        if(matrix[i]+matrix[j]<k) ++i;
        else if(matrix[i]+matrix[j]>k) --j;
        else{
            if(i==0 || matrix[i]!=matrix[i-1]){
                cout<<matrix[i]<<" "<<matrix[j]<<endl;
            }
            ++i;
            --j;
        }
    }
    return 0;
}

发表于 2021-07-11 10:53:55 回复(0)

不是VIP

这道题的测试用例是不是不全？

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

像这样的测试用例正确输出应该是

1 9

2 8

我的代码没有考虑这种情况也都AC了。

如下

#include<iostream>
#include<vector>
using namespace std;

int main()
{
    int n, k;
    int first = 0;
    cin>>n>>k;
    int last = n - 1;
    vector<int> arr(n);
    for(int i = 0; i < n; i++)
    {
        cin>>arr[i];
    }
    while(first < last)
    {
        if(arr[first]+arr[last] == k)
        {
            cout<<arr[first]<<" "<<arr[last]<<endl;
            while(arr[last] == arr[last-1])
            {
                last--;
            }
            last--;
            while(arr[first] == arr[first+1])
            {
                first++;
            }
            first++;
        }else{
            while(arr[first] == arr[first+1])
            {
                first++;
            }
            first++;
       }
    }
    return 0;
}

编辑于 2021-06-14 17:16:08 回复(0)

JavaScript

牛客6935520号

var lines=readline().split(' ')
var arr=readline().split(' ')
var l=0,r=lines[0]-1
while(l<r){
    if(parseInt(arr[l])+parseInt(arr[r])==lines[1]){
        if(l==0||arr[l]!=arr[l-1]){    //判断是否重复
            print(arr[l]+' '+arr[r])
        }
        l++
        r--
    } else if(arr[l]+arr[r]<lines[1]){
        l++
    } else {
        r--
    }
}

发表于 2020-08-23 11:17:28 回复(0)

是兄弟就一起加班

C++双指针方法

思路：由于给定数据是排好序的，可以直接用双指针。如果是未排序数据，用哈希表也能达到O(n)复杂度

#include <bits/stdc++.h>
using namespace std;

int main(){
    int n, k;
    cin>>n>>k;
    vector<int> v(n);
    for(int i=0;i<n;++i)
        cin>>v[i];
    int left=0, right=n-1;
    while(left < right){
        if(left>0 && v[left]==v[left-1]){  // 左指针遇到相等的元素直接跳过，避免答案出现重复组合
            ++left;
            continue;
        }
        // int sum = v[left] + v[right]; 这种写法有越界的风险
        int diff = k - v[left];
        if(diff == v[right]){
            cout<<v[left]<<" "<<v[right]<<endl;
            ++left;
        }
        else if(diff < right)
            --right;
        else
            ++left;
    }
    return 0;
}

发表于 2020-07-17 19:36:34 回复(0)

C/C++

Jason.LGY

这个题是一个典型的双指针的问题，左右向中间收缩，这样就可以保证不降序打印，同时为了保证不重复，应该在每次移动指针的时候直接移动到下一个不相等的位置：

#include <iostream>
#include <vector>

using namespace std;

int main(){
    
    int n, k;
    cin>>n>>k;
    vector<int> arr(n, 0);
    for(int i = 0; i < n; i++) cin>>arr[i];
    
    int l = 0, r = n-1, tmp;
    while(l < r){
        tmp = arr[l] + arr[r];
        if(tmp > k){
            r--;
            while(arr[r] == arr[r+1]) r--;
        }else if(tmp < k){
            l++;
            while(arr[l] == arr[l-1]) l++;
        }else{
            cout<<arr[l]<<' '<<arr[r]<<endl;
            l++; r--;
            while(arr[l] == arr[l-1]) l++;
            while(arr[r] == arr[r+1]) r--;
        }
    }
    return 0;
}

发表于 2020-07-10 16:13:13 回复(0)

程序猿的浪漫

#include <iostream>
#include <vector>
using namespace std;

int main(){
    int n,k;
    cin>>n>>k;
    vector<int>v(n);
    for(int i = 0;i<n;++i){
        cin>>v[i];
    }
    int left = 0,right = n-1;
    while(left < right){
        int cursum = v[left] + v[right];
        // 去除重复的值
        if(cursum == k){
            cout<<v[left]<<" "<<v[right]<<endl;
            ++left;
            while(v[left] == v[left-1]){
                ++left;
            }
            --right;
            while(v[right] == v[right+1]){
                --right;
            }
        }
        else if(cursum > k){
            --right;
        }else{
            ++left;
        }
    }
    return 0;
}

发表于 2020-07-04 17:05:24 回复(0)