每日一道 LeetCode (1):兩數(shù)之和
引言
前段時(shí)間看到一篇刷 LeetCode 的文章，感觸很深，我本身自己上大學(xué)的時(shí)候，沒(méi)怎么研究過(guò)算法這一方面，導(dǎo)致自己直到現(xiàn)在算法都不咋地。
一直有心想填補(bǔ)下自己的這個(gè)短板，實(shí)際上又一直給自己找理由各種推脫。
結(jié)果今天晚上吃多了，下定決心要刷一波 LeetCode 的題，刷題的過(guò)程順便寫(xiě)點(diǎn)文章分享下（其實(shí)有很好的督促作用）。
LeetCode 的背景啥的我就不多介紹了，我計(jì)劃只刷簡(jiǎn)單難度和中等難度的題，據(jù)說(shuō)刷了這兩個(gè)難度基本上就夠了，至于困難這個(gè)難度，先等我把前兩個(gè)部分刷完再說(shuō)。
大致聊一下刷題的套路，先看題目， 5 分鐘左右沒(méi)思路的直接看答案，這玩意沒(méi)思路是真沒(méi)辦法，沒(méi)有基礎(chǔ)儲(chǔ)備想做題還是有點(diǎn)困難的。
看完答案自己動(dòng)手寫(xiě)一下代碼，這一點(diǎn)很重要，現(xiàn)在面試很多白板代碼，一定要自己寫(xiě)，寫(xiě)會(huì)有效加深記憶力。
這個(gè)系列的文章計(jì)劃日更，原本以為不是一件很難的事情，結(jié)果當(dāng)我看到了這個(gè)：
1700+ 多道題，即使刨除掉困難的部分， 2/3 也有 1000+ 道題，我真的是給自己開(kāi)了一個(gè)非常棒的頭，這一下把未來(lái)兩三年的規(guī)劃都制定好了，我真是嗶了狗了。
不過(guò)不管怎么樣吧，決心都下好了，那么做還是要做的，對(duì)我這個(gè)計(jì)劃感興趣的同學(xué)可以每天在留言區(qū)和我一起打卡，預(yù)計(jì)每篇文章閱讀時(shí)長(zhǎng)在 3 分鐘左右，寫(xiě)代碼加調(diào)試代碼總時(shí)長(zhǎng)不會(huì)超過(guò)半小時(shí)。使用的代碼為 Java ，如果使用 Python 寫(xiě)的話有點(diǎn)太取巧了。
做事情，重要的是要堅(jiān)持。
需要代碼朋友可以訪問(wèn)我的 GitHub 和 Gitee 獲取，每天的代碼我會(huì)同步提交至這兩個(gè)代碼倉(cāng)庫(kù)：
GitHub：https://github.com/meteor1993/LeetCode
Gitee：https://gitee.com/inwsy/LeetCode
題目：兩數(shù)之和
給定一個(gè)整數(shù)數(shù)組 nums 和一個(gè)目標(biāo)值 target，請(qǐng)你在該數(shù)組中找出和為目標(biāo)值的那兩個(gè)整數(shù)，并返回他們的數(shù)組下標(biāo)。
你可以假設(shè)每種輸入只會(huì)對(duì)應(yīng)一個(gè)答案。但是，數(shù)組中同一個(gè)元素不能使用兩遍。
示例:
給定 nums = [2, 7, 11, 15], target = 9
因?yàn)?nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
思路
首先整理下思路，雖然題目的目標(biāo)是要求一個(gè)加法，使用程序直接寫(xiě)加法有點(diǎn)不是那么好寫(xiě)，稍微轉(zhuǎn)變一下，使用目標(biāo)值 target 減去數(shù)組 nums 中的一個(gè)值，如果得到的結(jié)果也在這個(gè)數(shù)組中，那么我們就解題完成。
暴力破解
我最先想到的也是最簡(jiǎn)單的方案，就是暴力破解，直接兩個(gè)循環(huán)套一下，暴力去算，得到結(jié)果：
public int[] twoSum_1(int[] nums, int target) {
for (int i = 0; i < nums.length; i++) {
int temp = target - nums[i];
for (int j = i + 1; j < nums.length; j++) {
if (nums[j] == temp) {
return new int[]{i, j};
}
}
}
throw new IllegalArgumentException("No two sum solution");
}
這種方案的缺點(diǎn)是時(shí)間復(fù)雜度有點(diǎn)高，優(yōu)點(diǎn)是簡(jiǎn)單，應(yīng)該是每個(gè)人都能想到的方案。
因?yàn)榭偣灿?n 個(gè)元素，而對(duì)于其中的每個(gè)元素來(lái)講，我們都需要遍歷整個(gè)數(shù)組來(lái)尋找是否存在它所需要的對(duì)應(yīng)的元素，這將耗費(fèi) O(n) 的時(shí)間。
時(shí)間復(fù)雜度：? 。
空間復(fù)雜度：O(1) 。
兩次哈希表
對(duì)暴力破解方案的優(yōu)化思路是，整個(gè)數(shù)組，至少需要迭代一次，關(guān)鍵是在這次迭代中，我們要尋找另一種方案，能比套一層循環(huán)更快更高效的找到檢查在整個(gè)數(shù)組中，是否含有我們需要的值。
我們可以借助哈希表來(lái)進(jìn)行尋找，它支持以 「近似」 恒定的時(shí)間進(jìn)行快速查找。
public int[] twoSum_2(int[] nums, int target) {
Map map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
map.put(nums[i], i);
}
for (int i = 0; i < nums.length; i++) {
int complement = target - nums[i];
if (map.containsKey(complement) && map.get(complement) != i) {
return new int[] {i, map.get(complement)};
}
}
throw new IllegalArgumentException("No two sum solution");
}
我們把包含有 n 個(gè)元素的列表遍歷兩次。由于哈希表將查找時(shí)間縮短到 O(1) ，所以時(shí)間復(fù)雜度為 O(n)。
時(shí)間復(fù)雜度：O(n) 。
空間復(fù)雜度：O(n) 。
一次哈希表：
上面我們是先把數(shù)組放到哈希表中，然后再進(jìn)行遍歷，實(shí)際上我們可以一邊放一邊進(jìn)行遍歷操作，直到某一個(gè)時(shí)刻，打成我們的目標(biāo)，這時(shí)我們可以直接返回?cái)?shù)據(jù)，剩下沒(méi)有放到哈希表中的數(shù)據(jù)也不用再往里面放了。
public int[] twoSum_3(int[] nums, int target) {
Map map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
int complement = target - nums[i];
if (map.containsKey(complement)) {
return new int[] { map.get(complement), i };
}
map.put(nums[i], i);
}
throw new IllegalArgumentException("No two sum solution");
}
雖然這種方式看著比前面的兩次哈希表更加的高效，實(shí)際上時(shí)間復(fù)雜度和空間復(fù)雜度是一致的，同樣是：
時(shí)間復(fù)雜度：O(n) 。
空間復(fù)雜度：O(n) 。
感謝閱讀