在数组中求出两个数，使他们的和等于给定的一个数

题目

给定一个整型数组和一个整数，要找出数组中的两个数字，使得这两个数字的和等于给定的和。

例如，输入数组numbers={1,2,3,4,5,6,7}，给定和为9，则要找出2和7，3和6，4和5的位置。

首先想到的是用两个for循环就能找出来。代码如下：

	/**
	 * 方法1，时间复杂度为O(n^2)		
	*/
	public int[] twoSumSolution1(int[] numbers,int sum) {
		int ret[] = new int[2];
		for (int i = 0; i < numbers.length; i++) {
			for(int j=i+1;j<numbers.length;j++){
				if (numbers[i]+numbers[j]==sum) {
					ret[0]=i+1;
					ret[1]=j+1;
				}
			}
		}
		return ret;		
	}

然而上述方法的时间复杂度为O(n^2)，很糟糕。于是想到用一个HashMap来解决，时间复杂度为O(n)。代码如下：

	public int[] twoSumSolution2(int[] numbers,int sum) {
		
		int[] ret=new int[2];
		HashMap<Integer, Integer>map=new HashMap<Integer,Integer>();		
		for (int i = 0; i < numbers.length; i++) {
			if (map.containsKey(numbers[i])) {	
			int index=map.get(numbers[i]);
			ret[0]=index+1;
			ret[1]=i+1;			
			}else {
				map.put(sum-numbers[i], i);//把总和减去当前数作为key放入map，然后与新进来的数字比对			
			}
		}
		return ret; 
    }

写一个总的测试代码如下：

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;

public class TwoSum {
	
	/**
	 * 方法1，时间复杂度为O(n^2)		
	*/
	public int[] twoSumSolution1(int[] numbers,int sum) {
		int ret[] = new int[2];
		for (int i = 0; i < numbers.length; i++) {
			for(int j=i+1;j<numbers.length;j++){
				if (numbers[i]+numbers[j]==sum) {
					ret[0]=i+1;
					ret[1]=j+1;
				}
			}
		}
		return ret;		
	}
	
	/**
	 * 方法2，时间复杂度为O(n)，利用HashMap，提高效率		
	*/
	public ArrayList<NumList> twoSumSolution2(int[] numbers,int sum) {
		//建一个ArrayList，里面有两个int[2]数组（num1[]和num2[]）
		ArrayList<NumList> indexsAndNum=new ArrayList<NumList>();
		HashMap<Integer, Integer>map=new HashMap<Integer,Integer>();		
		for (int i = 0; i < numbers.length; i++) {
			if (map.containsKey(numbers[i])) {
				//num1[0]和num1[1]存储第一个数的位置和值，num2[0]和num2[1]存储第二个数的位置和值。
				int num1[]=new int[2];
				int num2[]=new int[2];
				int index=map.get(numbers[i]);
				num1[0]=index+1;num1[1]=numbers[index];
				num2[0]=i+1;num2[1]=numbers[i];	
				NumList numList=new NumList(num1, num2);//把符合要求的数对存储到ArrayList里面
				indexsAndNum.add(numList);
			}else {
				map.put(sum-numbers[i], i);//把总和减去当前数作为key放入map，然后与新进来的数字比对
				continue;
			}
		}
		return indexsAndNum;		
	}
	/**
	 * 输出满足条件的数的位置和数值
	*/
	public void testForEach(ArrayList<NumList> indexsAndNum){
		System.out.println("符合条件的数对有：");
		for (Object obj:indexsAndNum) {
			NumList temp=(NumList) obj;
			System.out.println("第"+temp.num1[0]+"个数字 ‘"+temp.num1[1]+"’ 与 "+"第"+temp.num2[0]+"个数字 ‘"+temp.num2[1]+"’。");
		}
	}

	public static void main(String[] args) {
		int[] numbers={1,3,2,11,5,6,7,9,8,10};
		int sum=12;
		System.out.println("输入的数组是："+Arrays.toString(numbers)+" ;给定的和是："+sum);
		TwoSum testTwoSum=new TwoSum();
		ArrayList<NumList> indexsAndNum=testTwoSum.twoSumSolution2(numbers, sum);
		testTwoSum.testForEach(indexsAndNum);		
	}
}

其中，NumList是这样定义的：

public class NumList {
	
	public int[] num1;//第一个加数的位置和值
	public int[] num2;//第二个加数的位置和值
	
	public NumList(int[] num1,int[] num2) {
		this.num1=num1;
		this.num2=num2;
	}

}

运行上述代码，得到结果是：

输入的数组是：[1, 3, 2, 11, 5, 6, 7, 9, 8, 10] ;给定的和是：12
符合条件的数对有：
第1个数字 ‘1’ 与 第4个数字 ‘11’。
第5个数字 ‘5’ 与 第7个数字 ‘7’。
第2个数字 ‘3’ 与 第8个数字 ‘9’。
第3个数字 ‘2’ 与 第10个数字 ‘10’。