两数之和

1.题目描述：给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。

你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。

示例:

给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
2.解答：

package algorithm;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.InputMismatchException;
import java.util.List;
import java.util.Scanner;

public class TwoSum {
	public static void main(String args[]) {
		int temp,target;
		ArrayList arraylist = new ArrayList();
		Scanner reader = new Scanner(System.in);
		System.out.println("请输入一个数组，按回车键结束：");
		String s = reader.nextLine();
		Scanner reader2 = new Scanner(s);
		//以下将字符转换回整数存入数组（将数字抽取出来）
		while(reader2.hasNext()) {
			try {
				int num=reader2.nextInt();
				arraylist.add(num);
			}catch(InputMismatchException exp) {
				String t=reader2.next();
			}
		}
		//将arraylist转换为int[]型数组，以便和参数相对应；
		int [] intArray = new int[arraylist.size()];
		for(int i=0;i<arraylist.size();i++) {
			intArray[i]=(int) arraylist.get(i);
		}
		System.out.println("输入目标数：");
		target=reader.nextInt();
		Solution solution=new Solution();
		int [] result = solution.twoSum(intArray, target);
		System.out.println("返回结果：");
		System.out.println(Arrays.toString(result));
	}
}

class Solution{
	public int[] twoSum(int[] nums, int target) {
		int [] result = new int[2];
		for(int i=0;i<nums.length;i++) {
			for(int j=i+1;j<nums.length;j++) {
				if(nums[i]+nums[j]==target) {
					result[0]=i;result[1]=j;
					return result;
				}
			}
		}
		return result;
	}
}

测试结果如下：

3.分析：题目的解答实际上就Solution一个类，用的是暴力求解，很简单，自己卡在测试上，即怎样输入一个动态数组进行测试：先输入一行字符，再将字符里面的数字逐个读出存进数组，最后再将新建一个int[]型数组将arraylist里面的整数读取进来；
暴力解法的时间复杂度是O（n2）；看了下其他解法后发现可以用HashMap进行查找，方法如下：
一.两遍哈希表：

public int[] twoSum(int[] nums, int target) {
    Map<Integer, Integer> map = new HashMap<>();
    for (int i = 0; i < nums.length; i++) {
        map.put(nums[i], i);
    }
    for (int i = 0; i < nums.length; i++) {
        int complement = target - nums[i];
        if (map.containsKey(complement) && map.get(complement) != i) {
            return new int[] { i, map.get(complement) };
        }
    }
    throw new IllegalArgumentException("No two sum solution");
}

时间复杂度：O(n)；
空间复杂度：O(n)，取决于存储元素数量；

二.一遍哈希表：

public int[] twoSum(int[] nums, int target) {
    Map<Integer, Integer> map = new HashMap<>();
    for (int i = 0; i < nums.length; i++) {
        int complement = target - nums[i];
        if (map.containsKey(complement)) {
            return new int[] { map.get(complement), i };
        }
        map.put(nums[i], i);
    }
    throw new IllegalArgumentException("No two sum solution");
}

时间复杂度：O(n)。

空间复杂度：O(n)。

PS：

public class Test {
	public static void main(String args[]) {
		int [] array=new int[] {1,2};
		/*
		 * {1,2}是new int[]{1,2}的简写，但该简写只能用于同类型变量的简写，
		 * 如果 int [] array;array={1,2}则错误；而int [] array={1,2}则正确；
		 */
	}
}