問題描述：在一個整數數組中，找到兩數之和為target的兩個值，返回找到的兩個值的下標。

nums=[3,3]

target=6

返回：[0,1]

說明：返回結果，索引無順序要求；有唯一的答案；不能使用兩次相同的元素，比如上述例子中不能返回[0,0]或者[1,1]。

---

求解思路1：暴力解法

兩層for循環

時間復雜度：O(n^2)

空間復雜度：O(1)

class Solution {public int[] twoSum(int[] nums, int target) {int[] indexArr = 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){indexArr[0] = i;indexArr[1] = j;break;}}}return indexArr;}
}

---

求解思路2：使用哈希

把所有值都存到哈希表中，key為num，value為index。找兩數，其實就是遍歷的時候查找target-nums[i]，去哈希表中查找即可。

時間復雜度：O(1)

空間復雜度：O(n)

class Solution {public int[] twoSum(int[] nums, int target) {int[] indexArr = new int[2];HashMap<Integer,Integer> hashMap = new HashMap<>();// 把所有的數都存放到hashMap中for(int i = 0;i < nums.length;i++){hashMap.put(nums[i],i);}for(int i = 0;i < nums.length;i++){int curNum = nums[i];int another = target - curNum;// 尋找另一個數時，必須要有i != hashMap.get(another)// 否則[3,2,4]這種情況會返回[0,0]而報錯if(hashMap.containsKey(another) && i != hashMap.get(another)){indexArr[0] = i;indexArr[1] = hashMap.get(another);break;}}return indexArr;}
}

上面的代碼是構建hash表、遍歷查找另一個數，分開了兩步，也可以在一個for循環里進行，如下：

class Solution {public int[] twoSum(int[] nums, int target) {int[] indexArr = new int[2];HashMap<Integer,Integer> hashMap = new HashMap<>();hashMap.put(nums[0],0);for(int i = 0;i < nums.length;i++){int curNum = nums[i];int another = target - curNum;if(hashMap.containsKey(another) && i != hashMap.get(another)){indexArr[0] = i;indexArr[1] = hashMap.get(another);break;}hashMap.put(nums[i],i);}return indexArr;}
}

練習地址：1. 兩數之和 - 力扣（LeetCode）