前言
我從兩周前開始接觸算法，從一周前開始接觸leetcode致燥。我主要使用leetcode練習(xí)算法題目登疗，本沒(méi)有記錄一番的打算，正巧加入了耗子叔的左耳聽(tīng)風(fēng) ARTS專欄嫌蚤，其中的A就是每周一道leetcode算法題辐益，并且需要記錄下來(lái)分享，于是開始了leetcode做題記錄的第一篇脱吱。
在文章中我不會(huì)只是簡(jiǎn)單記錄答案智政，我會(huì)寫下自己解題思路的變化，同時(shí)也會(huì)對(duì)復(fù)雜的代碼處進(jìn)行解釋箱蝠，因?yàn)閯傞_始接觸算法題目续捂，所以從easy級(jí)別的開始，有復(fù)雜代碼的可能性比較低宦搬，接下來(lái)直接上題目牙瓢。
題目 兩數(shù)之和 題號(hào)#1
查看題目可點(diǎn)擊此處。
給定一個(gè)整數(shù)數(shù)組 nums 和一個(gè)目標(biāo)值 target床三，請(qǐng)你在該數(shù)組中找出和為目標(biāo)值的那兩個(gè) 整數(shù)一罩，并返回他們的數(shù)組下標(biāo)。
你可以假設(shè)每種輸入只會(huì)對(duì)應(yīng)一個(gè)答案撇簿。但是聂渊，你不能重復(fù)利用這個(gè)數(shù)組中同樣的元素差购。
示例:
給定 nums = [2, 7, 11, 15], target = 9
因?yàn)?nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
解題思路
讀懂題目的第一思路就是利用兩個(gè)循環(huán)對(duì)數(shù)組的元素進(jìn)行加和，與target比對(duì)判斷汉嗽，成功就返回?cái)?shù)組兩個(gè)元素下標(biāo)欲逃，代碼如下：
class Solution {
public int[] twoSum(int[] nums, int target) {
int i = 0, j = i + 1;
for(; i < nums.length - 1; i++) {
for(j = i + 1; j < nums.length; j++) {
if(nums[j] + nums[i] == target) {
return new int[] {i, j};
}
}
}
return null;
}
}
這段代碼時(shí)間復(fù)雜度是O(n2)，應(yīng)該還有更優(yōu)的解饼暑。轉(zhuǎn)換思路稳析，其實(shí)結(jié)果是返回滿足條件的元素下標(biāo)，元素與下標(biāo)需要關(guān)聯(lián)上弓叛，又可以快速通過(guò)元素返回下標(biāo)的方式讓我想到了Map彰居。代碼如下：
class Solution {
public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> map = new HashMap<>(nums.length);
for(int i = 0; i < nums.length && nums[i] <= target; i++) {
map.put(nums[i], i);
}
for(Map.Entry<Integer, Integer> entry : map.entrySet()) {
Integer index = map.get(target - entry.getKey());
if(index != null) {
return new int[] {entry.getValue(), index};
}
}
return null;
}
}
滿心歡喜以為找到了O(n)時(shí)間復(fù)雜度的解法，結(jié)果這個(gè)提交失敗撰筷，失敗示例如下
輸入：
[3,3]
6
輸出：
[1,1]
預(yù)期：
[0,1]
究其原因陈惰，數(shù)組中的元素重復(fù)，Map中的key產(chǎn)生覆蓋毕籽，而又使用Map進(jìn)行遍歷抬闯，無(wú)法遍歷到數(shù)組所有元素，并且未判斷是否重復(fù)使用一個(gè)數(shù)組元素進(jìn)行加和滿足條件关筒，導(dǎo)致出現(xiàn)此問(wèn)題溶握。于是繼續(xù)改進(jìn)代碼：
class Solution {
public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> map = new HashMap<>(nums.length / 3);
for(int i = 0; i < nums.length && nums[i] <= target; i++) {
map.put(nums[i], i);
}
for(int i = 0; i < nums.length; i++) {
int otherNum = target - nums[i];
if(map.containsKey(otherNum) && map.get(otherNum) != i) {
return new int[] {i, map.get(otherNum)};
}
}
return null;
}
}
將遍歷map修改為遍歷數(shù)組本身，雖然還是會(huì)有數(shù)組元素重復(fù)導(dǎo)致key覆蓋蒸播，但是只要能找出一對(duì)滿足加和為target條件的元素下標(biāo)即可睡榆，所以map的key因重復(fù)數(shù)組元素導(dǎo)致覆蓋也就不影響結(jié)果，并且在第10行代碼上加入了對(duì)是否重復(fù)使用一個(gè)數(shù)組元素進(jìn)行加和的判斷袍榆。其實(shí)肉微，這段代碼也失敗了，失敗樣例如下：
輸入：
[-1,-2,-3,-4,-5]
-8
輸出：
[0,0]
預(yù)期：
[2,4]
原因是第4行代碼處增加了nums[i] <= target的判斷蜡塌，我認(rèn)為相加之和等于target的兩數(shù)必然小于或等于target，想利用些條件減少map中的數(shù)據(jù)量勿负，卻忽略了負(fù)數(shù)的可能性馏艾。根據(jù)問(wèn)題修改代碼：
class Solution {
public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> map = new HashMap<>(nums.length / 3);
for(int i = 0; i < nums.length; i++) {
map.put(nums[i], i);
}
for(int i = 0; i < nums.length; i++) {
int otherNum = target - nums[i];
if(map.containsKey(otherNum) && map.get(otherNum) != i) {
return new int[] {i, map.get(otherNum)};
}
}
return null;
}
}
這段代碼可以成功通過(guò)所有測(cè)試樣例，而且時(shí)間也比雙循環(huán)時(shí)提高了許多奴愉。
根據(jù)官方還有一個(gè)更優(yōu)的解琅摩，就是在循環(huán)的同時(shí)對(duì)map進(jìn)行判斷，不滿足條件便放入map锭硼，滿足條件就返回結(jié)果房资。代碼如下：
class Solution {
public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> map = new HashMap<>(nums.length / 3);
for(int i = 0; i < nums.length; i++) {
int otherNum = target - nums[i];
if(map.containsKey(otherNum)) {
return new int[] {map.get(otherNum), i};
}
map.put(nums[i], i);
}
return null;
}
}
通過(guò)幾天的解題發(fā)現(xiàn)自己對(duì)題目樣例中可能出現(xiàn)的特殊情況缺少考慮，對(duì)操作的簡(jiǎn)化也還需要更深入的思考檀头。
