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

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

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

备注:

算法知识视频讲解

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)

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)

Java

田野畅通无阻

一开始真的没看到不重复输出，一直卡在0%（哭）

public static void main(String[] args){
    Scanner scanner = new Scanner(System.in);
    int n=scanner.nextInt(),k=scanner.nextInt();
    int[] ma = new int[n];
    for(int i=0;i<n;i++)
        ma[i] = scanner.nextInt();
    int i=0,j=n-1,sum=-1;
    while(i<j){
        long temp = ma[i]+ma[j];
        if (temp == k) {
            if(sum==-1||ma[i]!=ma[sum]){
                System.out.printf("%d %d\n", ma[i], ma[j]);
                sum = i;i++;j--;
            }else
                i++;
        } else if (temp < k) {
            i++;
        } else
            j--;
    }
}

发表于 2019-09-07 15:28:18 回复(0)