14.输入一个已经按升序排序过的数组和一个数字， 在数组中查找两个数，使得它们的和正好是输入的那个数字。 要求时间复杂度是O(n)
浏览数：38 /
时间：2015年06月08日
待完善！
转载请注明出处：http://www.cnblogs.com/wuzetiandaren/p/4259199.html
声明：现大部分文章为寻找问题时在网上相互转载，此博是为自己做个记录记录，方便自己也方便有类似问题的朋友，本文的思想也许有所借鉴，但源码均为本人实现，如有侵权，请发邮件表明文章和原出处地址，我一定在文章中注明。谢谢。
题目：
输入一个已经按升序排序过的数组和一个数字，
在数组中查找两个数，使得它们的和正好是输入的那个数字。
要求时间复杂度是O(n)。如果有多对数字的和等于输入的数字，输出任意一对即可。
例如输入数组1、2、4、7、11、15和数字15。由于4+11=15，因此输出4和11。
我觉得输出下标更为合理
借鉴快速排序的思想：
（1）让指针指向数组的头部和尾部，相加，如果小于M，则增大头指针，如果大于则减小尾指针
（2）退出的条件，相等或者头部=尾部
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 }
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
郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。
