51nod --1001 数组中和等于K的数对(一级算法题)

1001 数组中和等于K的数对

基准时间限制：1 秒 空间限制：131072 KB 分值: 5 难度：1级算法题 收藏 关注
给出一个整数K和一个无序数组A，A的元素为N个互不相同的整数，找出数组A中所有和等于K的数对。例如K = 8，数组A：{-1,6,5,3,4,2,9,0,8}，所有和等于8的数对包括(-1,9)，(0,8)，(2,6)，(3,5)。
Input
第1行：用空格隔开的2个数，K N，N为A数组的长度。(2 <= N <= 50000，-10^9 <= K <= 10^9)
第2 - N + 1行：A数组的N个元素。（-10^9 <= A[i] <= 10^9)
Output
第1 - M行：每行2个数，要求较小的数在前面，并且这M个数对按照较小的数升序排列。
如果不存在任何一组解则输出：No Solution。
Input示例
8 9
-1
6
5
3
4
2
9
0
8
Output示例
-1 9
0 8
2 6
3 5

个人解题思路

/*
个人解题思路：由于观察数据量50000，可知(n2)的复杂度，肯定会超时，于是想到了(nlogn)，便想到了二分，于是，便想到了a+b=k;那么b=k-a；又由于输出条件要从小到大，便想到了排序，
刚好二分查找也要求有序，于是问题：便变成了，从一个有序数组查找一个数
*/

代码

import java.util.*;
public class Main{
    static int n;
    static int index =0; //记录要查找那个数的下标
    //为什么要找他下标呢？因为用过一次的就要记录下来，下次不能要用了
    static int[] arr = null;
    static int[] vis = null;
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int k = sc.nextInt();
        n = sc.nextInt();
        arr = new int[n];
        vis = new int[n];
        //input
        for(int i=0; i<n; ++i)
            arr[i] = sc.nextInt();
        //process
        Arrays.sort(arr);
        boolean flag = false;
        for(int i=0; i<n; ++i)
        if(vis[i] == 0){
            vis[i] = 1;
            int res = k - arr[i];
            boolean tag = find_res(res,i);
            if(tag){
                System.out.println(arr[i] + " " + res );
                vis[index] = 1;
                flag = true;
            }
            else
                continue;
        }
        if(flag == false)
            System.out.println("No Solution");
    }
    public static boolean find_res(int num, int in){
        int i = 0;
        int j = n-1;
        int mid = 0;
        boolean tag = false;
        while(i <= j){
            mid = i + (j-i)/2;
            if(arr[mid] < num){
                i = mid + 1;
            }else if(arr[mid] > num){
                j = mid - 1;
            }else{
                index = mid;
                tag = true;
                break;
            } 
        }
        if(tag == true && in != index) //去掉相同的，比如8=4+4，但是4只有一个的情况
            return true;
        return false;
    }
}