?1.題目

給定一個(gè)整數(shù)數(shù)組 nums?和一個(gè)整數(shù)目標(biāo)值 target，請(qǐng)你在該數(shù)組中找出 和為目標(biāo)值 target? 的那?兩個(gè)?整數(shù)，并返回它們的數(shù)組下標(biāo)。

你可以假設(shè)每種輸入只會(huì)對(duì)應(yīng)一個(gè)答案。但是，數(shù)組中同一個(gè)元素在答案里不能重復(fù)出現(xiàn)。

你可以按任意順序返回答案。

2.示例

示例 1：

輸入：nums = [2,7,11,15], target = 9
輸出：[0,1]
解釋：因?yàn)?nums[0] + nums[1] == 9 ，返回 [0, 1] 。

?示例 2：

輸入：nums = [3,2,4], target = 6
輸出：[1,2]

?示例 3：

輸入：nums = [3,3], target = 6
輸出：[0,1]

提示：

• 2 <= nums.length <= 104
• -109 <= nums[i] <= 109
• -109 <= target <= 109
• 只會(huì)存在一個(gè)有效答案

---

3.思路

兩種解法：

1.暴力遍歷

通過(guò)遍歷nums和對(duì)nums的每一個(gè)元素與后續(xù)的元素之間組合查看是否和值為target

2.哈希表查找

通過(guò)建立哈希表，并且只需要一次遍歷所有nums，將nums的所有前面的值的鍵值和數(shù)值都存放在哈希表中，在遍歷時(shí)候可以通過(guò)查詢哈希表中是否存在target減去當(dāng)前的值的數(shù)，若存在則返回鍵值所對(duì)應(yīng)的下角標(biāo)。

4.代碼

LeetCode代碼

暴力遍歷

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

時(shí)間復(fù)雜度O(n^2)空間復(fù)雜度O(1) ,空間優(yōu)解

哈希表查找

class Solution {public int[] twoSum(int[] nums, int target) {Map<Integer,Integer> map = new HashMap<>();for (int i=0;i< nums.length;i++){if (map.containsKey(target - nums[i])){return new int[]{map.get(target-nums[i]),i};}map.put(nums[i],i);}return new int[2];}
}

?時(shí)間復(fù)雜度O(n),空間復(fù)雜度O(n^2)時(shí)間優(yōu)解