題目信息
給定一個整數(shù)數(shù)組 nums 和一個目標值 target烂翰，請你在該數(shù)組中找出和為目標值的那 兩個 整數(shù)，并返回他們的數(shù)組下標蚤氏。
你可以假設每種輸入只會對應一個答案甘耿。但是，你不能重復利用這個數(shù)組中同樣的元素竿滨。
示例:
給定 nums = [2, 7, 11, 15], target = 9
因為 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/two-sum
著作權歸領扣網(wǎng)絡所有佳恬。商業(yè)轉載請聯(lián)系官方授權，非商業(yè)轉載請注明出處于游。
題目解答
解法一：“暴力破解”
拿到題目毁葱，第一反應是暴力破解...雙層for循環(huán)，一個一個的往后遍歷贰剥，時間復雜度為O(n^2)头谜，空間復雜度為O(1)，代碼如下：
/**
* 最粗暴的解決方案鸠澈，雙層遍歷循環(huán)
* 時間復雜度 ： O(n^2)柱告，雙層循環(huán)
* 空間復雜度 ： O(1)截驮，只需要一個臨時變量來存儲
*
* @param nums
* @param target
* @return
*/
public int[] twoSumByViolence(int[] nums, int target) {
if (nums == null || nums.length < 2)
throw new IllegalArgumentException("數(shù)組長度錯誤！际度！");
int numsLength = nums.length;
int target1 = 0;
for (int i = 0; i < numsLength; i++) {
target1 = nums[i];
for (int j = i + 1; j < numsLength; j++) {
if (nums[j] == target - target1)
return new int[]{i, j};
}
}
throw new IllegalArgumentException("沒有符合條件的結果葵袭！");
}
解法二：“空間換時間”(哈希)
暴力破解的方式，時間復雜度為O(n^2)乖菱，耗時較長坡锡，分析題目可以知道我們實際要做的工作就是拿著一個變量找到另外一個遍歷相加等于target并返回它們的索引，尋找另外一個變量消耗了O(n)的時間窒所，我們可以利用hash表來降低查找時間鹉勒。hash表維持近似恒定（發(fā)生沖突會變成O(n)）效率進行查詢，所以hash算法的選擇會決定查詢時間吵取。
在第一次迭代中禽额，將值和索引放到哈希表中，在第二次迭代中皮官，檢查目標值（target - nums[i]）是否存在于表中且該值不是nums[i]本身脯倒。代碼如下：
/**
* 利用map，
* 這種方式存在問題：若數(shù)組存在相同的數(shù)據(jù)捺氢，后面的索引會在put的時候覆蓋掉前面的索引
* 如：{2,2,5,4,1} 7 會返回 {1,2}藻丢，并不會返回{0,2}
* 時間復雜度 ： O(n)
* 空間復雜度 ： O(n)
* 題目中有標出**可以假設每種輸入只會對應一個答案**，所以不會存在描述的問題
*
* @param nums
* @param target
* @return
*/
public int[] twoSumByTwoHash(int[] nums, int target) {
if (nums == null || nums.length < 2)
throw new IllegalArgumentException("數(shù)組長度錯誤Ｉ闫埂悠反！");
Map<Integer, Integer> map = new HashMap<Integer, Integer>();
int numsLength = nums.length;
for (int i = 0; i < numsLength; i++) {\\第一次迭代中，將值和索引放到哈希表中
map.put(nums[i], i);
}
int target1 = 0;
//第二次迭代中馍佑，檢查目標值（target - nums[i]）是否存在于表中且該值不是nums[i]本身
for (int i = 0; i < numsLength; i++) {
target1 = target - nums[i];
if (map.containsKey(target1) && map.get(target1) != i)
return new int[]{i, map.get(target1)};
}
throw new IllegalArgumentException("沒有符合條件的結果斋否！");
}
解法三：優(yōu)化后的哈希
在解法二中我們利用了HashMap的特性降低了查詢時間，但我們可以同時進行將放入哈希表和檢查目標值兩個步驟挤茄，代碼如下：
/**
* 單次Hash算法求和
* 問題：數(shù)據(jù)重復時如叼，不能保證輸出順序
* [3,4,4,7,2,11,15]
* 8
* [2,1]
* [1,2]
* 時間復雜度 ： O(n)
* 空間復雜度 ： O(n)
*
* @param nums
* @param target
* @return
*/
public int[] twoSumByOneHash(int[] nums, int target) {
if (nums == null || nums.length < 2)
throw new IllegalArgumentException("數(shù)組長度錯誤１尽穷劈！");
Map<Integer, Integer> map = new HashMap<Integer, Integer>();
int numsLength = nums.length;
int target1 = 0;
for (int i = 0; i < numsLength; i++) {
target1 = target - nums[i];
if (map.containsKey(target1))
return new int[]{i, map.get(target1)};
map.put(nums[i], i);
}
throw new IllegalArgumentException("沒有符合條件的結果！");
}
