编程题目解析

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

 

import java.util.ArrayList;
import java.util.List;

public class GetNumInList {
	
	class Pair{
		private int a;
		private int b;
		public Pair(int a,int b){
			this.a=a;
			this.b=b;
		}
		@Override
		public String toString() {
			return "[" + a + ", " + b + "]";
		}
		
	}
	
	/**
	 * 从数组中找到一对数字的和与指定值相同
	 * @param orignal 待查找的数组
	 * @param found   待查找的数字
	 * @return
	 */
	public static List<Pair> findNum(List<Integer> orignal, int found) {
		List<Pair> result = new ArrayList<Pair>();
		int current = 0, last = 0;
		int length = orignal.size();

		for (int i = 0; i < length; i++) {
			current = i;
			last = i + 1;

			while (last <= length - 1) {
				if (found == (orignal.get(current) + orignal.get(last))) {
					result.add(new GetNumInList().new Pair(orignal.get(current),orignal.get(last)));
				}
				last++;
			}

		}
		return result;
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		List<Integer> list = new ArrayList<Integer>();
		for (int i = 1; i < 10; i++) {
			list.add(i);
		}
		
		List<Pair> result=GetNumInList.findNum(list, 10);
		
		for(Pair pair:result){
			System.out.println(pair);
		}
	}

}