首页 > 代码库 > 14.输入一个已经按升序排序过的数组和一个数字， 在数组中查找两个数，使得它们的和正好是输入的那个数字。 要求时间复杂度是O(n)
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）让指针指向数组的头部和尾部，相加，如果小于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 args14 */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 args14 */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
14.输入一个已经按升序排序过的数组和一个数字， 在数组中查找两个数，使得它们的和正好是输入的那个数字。 要求时间复杂度是O(n)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。