文章收錄于LeetCode專欄
LeetCode地址

---

兩數(shù)之和

??給定一個(gè)整數(shù)數(shù)組nums和一個(gè)整數(shù)目標(biāo)值target，請(qǐng)你在該數(shù)組中找出和為目標(biāo)值的那兩個(gè)整數(shù)，并返回它們的數(shù)組下標(biāo)。
??你可以假設(shè)每種輸入只會(huì)對(duì)應(yīng)一個(gè)答案。但是數(shù)組中同一個(gè)元素在答案里不能重復(fù)出現(xiàn)。你可以按任意順序返回答案。
??示例 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]

題解

第一步審題

??給定一個(gè)數(shù)組求得其中任意兩數(shù)之和為目標(biāo)值，題目很簡(jiǎn)單就是從數(shù)組中得得等于目標(biāo)值的元素的下標(biāo)。

第二步列出所有解

??求解該題目可以采用暴力求解和hash表兩種方式。

解法一（暴力枚舉）

??所謂暴力枚舉就是采用兩層循環(huán)，每層循環(huán)取出數(shù)組中一個(gè)元素，判斷兩層循環(huán)取出的兩個(gè)元素相加是否等于目標(biāo)值。

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

解法二（hash表）

??暴力枚舉法采用了兩層循環(huán)時(shí)間復(fù)雜度較高，所以可以采用采用的空間換時(shí)間的方式，定義一個(gè)hash表來(lái)記錄遍歷過程中用過的元素及其下標(biāo)，這樣再下一輪判斷的時(shí)候可以直接通過map.get(y)= target-x來(lái)判斷是否等于目標(biāo)值。

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

第三步復(fù)雜度分析

??暴力枚舉法使用了兩層循環(huán)且沒有使用額外的內(nèi)存空間，所以時(shí)間復(fù)雜度為O(n²)，空間復(fù)雜度為O(1)；hash表使用空間換時(shí)間的方法，所以時(shí)間復(fù)雜度為O(n)，空間復(fù)雜度為O(n)。

---

一鍵三連，讓我的信心像氣球一樣膨脹！