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; }}
