leetcode 1. TwoSum
问题描述：
Given an array of integers, return indices of the two numbers such that they add up to a specific target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.
Example: Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9, return [0, 1].
思路
方法1：
一种相对直接的方法，分两层遍历数组，如果两个数的结果等于目标数则返回，时间复杂度为O(n^2)
代码：
/** * Created by Henry on 2017/1/16. */public class TwoSum { public static void main(String[] ages){ int[] nums = {1,3,5,9}; int target = 8; int [] results = new int[2]; results = twoSum(nums, target); System.out.PRintln(results[0]); System.out.println(results[1]); } public static int[] twoSum(int[] nums, int target){ int[] results = new int[2]; int flag = 0; for(int i=0;i < nums.length; i++){ if(flag != 0) break; for(int j = i+1; j < nums.length; j++){ if(nums[i]+nums[j] == target){ results[0] = i; results[1] = j; flag = 1; break; } } } return results; }}方法2：
希望能够通过一次遍历求得结果。引入Map数据结构，每次遍历时以数组的数字为key，索引为value放入map(这种map在考察数组的算法题中比较常见)中，每次遍历数字前首先判断目标数字与要遍历的数字的差是否在map中，如果不在则继续遍历，否则在map中则找到了第二个数字，将这个数字的索引放入结果数组中，再以目标数字与这个数字的差为key得到第一数字的索引位置并放入结果数组中。这种方法的时间复杂度为O（n）,时间复杂度降低了，但是引入了map数据结构，以牺牲空间为代价来降低运行时间。
代码：
import java.util.HashMap;import java.util.Map;/** * Created by Henry on 2017/2/18. */public class TwoSum2 { public static void main(String[] args){ int [] nums = {1, 3, 5, 9}; int [] results = new int[2]; int target = 8; TwoSum2 twosum2 = new TwoSum2(); results = twosum2.twoSum(nums, target); System.out.println(results[0]+","+results[1]); } public int[] twoSum(int[] nums, int target){ int[] results = new int[2]; Map<Integer,Integer> map = new HashMap<Integer,Integer>(); for(int i = 0; i < nums.length; i++){ if(map.containsKey(target - nums[i])){ results[1] = i; results[0] = map.get(target-nums[i]); return results; } map.put(nums[i], i); } return results; }}
