14.输入一个已经按升序排序过的数组和一个数字, 在数组中查找两个数,使得它们的和正好是输入的那个数字。 要求时间复杂度是O(n)

转载请注明出处:http://www.cnblogs.com/wuzetiandaren/p/4259199.html 

声明:现大部分文章为寻找问题时在网上相互转载,此博是为自己做个记录记录,方便自己也方便有类似问题的朋友,本文的思想也许有所借鉴,但源码均为本人实现,如有侵权,请发邮件表明文章和原出处地址,我一定在文章中注明。谢谢。

题目:输入一个已经按升序排序过的数组和一个数字,在数组中查找两个数,使得它们的和正好是输入的那个数字。要求时间复杂度是O(n)。如果有多对数字的和等于输入的数字,输出任意一对即可。例如输入数组1、2、4、7、11、15和数字15。由于4+11=15,因此输出4和11。

题目分析:

  个人觉得这个题目可以完善一下:找出所有满足条件的元素对的下标及其对应的值。因此我的代码是这样实现的,当然只需做一点点小改造就可以实现成原题目的要求,这个在源码的注释里已经给出提示。

要实现这个题目,可以借鉴一下快速排序的一次扫描算法的思想:

  1.用两个标记指针i,j,初始化i=0, j=n-1,  n为数组的长度。

  2。当i<j时,

    a.当i<j并且a[i]与a[j]之和大于期望值,则j--

    b.如果i<j并且a[i]与a[j]之和等于期望值,则保存结果, i++

    c.当i<j并且a[i]与a[j]之和小于期望值,则 i++

    d.如果i<j并且a[i]与a[j]之和等于期望值,则保存结果, j--

java实现源码:

 1 package com.interview;
 2 
 3 import java.util.HashMap;
 4 /**
 5  * 题目:输入一个已经按升序排序过的数组和一个数字,在数组中查找两个数,
 6  *     使得它们的和正好是输入的那个数字。要求时间复杂度是O(n)。
 7  * @author wjh
 8  *
 9  */
10 public class _14AscSortSum {
11 
12     /**
13      * @param args
14      */
15     public static void main(String[] args) {
16         // 
17         _14AscSortSum sum = new _14AscSortSum();
18         int[] a = {-3,-2,0,1,2,3,6,7,9,15,17,19};
19         HashMap<Integer,Integer> map = new HashMap<Integer,Integer>();
20         map = sum.searchSum(a,9,map);  //1)查找
21         sum.printResult(a,map);          //打印查找结果
22     }
23     
24     
25     //查找 ,下标从0开始
26     private HashMap<Integer,Integer> searchSum(int[] a, int Num, HashMap<Integer,Integer> map){
27         int n = a.length;
28         int i=0,j=n-1;   //i和j分别保存当前较小的和交大的数据
29         //Map map = new HashMap<Integer,Integer>();
30         while(i<j){       //查找条件
31             while(i<j && (a[i]+a[j])>Num){
32                 j--;
33             }
34             if(i<j&&(a[i]+a[j])==Num){
35                 map.put(i, j);
36                 i++;
37                 //return map;   //如果找到就结束的话加上这句
38             }
39             while(i<j && (a[i]+a[j])<Num){
40                 i++;
41             }
42             if(i<j&&(a[i]+a[j])==Num){
43                 map.put(i, j);
44                 j--;
45                 //return map;   //如果找到就结束的话加上这句
46             }
47         }
48         return map;
49     }
50     
51     //打印查找结果
52     private void printResult(int[] a, HashMap<Integer,Integer> map){
53         int n = map.size();
54         if(n==0){
55             System.out.println("没有找到!");
56             return;
57         }
58         System.out.println("这是找到的所有元素:");
59         for(Integer key: map.keySet()){
60             System.out.println("下标为:("+key+","+map.get(key)+"),    值为:"+a[key]+","+a[map.get(key)]);
61         }
62     }
63 
64 }
完整源码

运行结果:

这是找到的所有元素:
下标为:(2,8), 值为:0,9
下标为:(4,7), 值为:2,7
下标为:(5,6), 值为:3,6