簡單算法第一天---兩數(shù)之和(TwoSum)

小小程序員的我準(zhǔn)備沒事刷刷leetcode的題多望,順便把當(dāng)時(shí)的想法記錄~

英文原題? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? Two Sum

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example:

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,

return [0, 1].

中文翻譯

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 兩數(shù)之和

給定一個(gè)整數(shù)數(shù)組和一個(gè)目標(biāo)值确徙,找出數(shù)組中和為目標(biāo)值的 兩個(gè) 數(shù)。

你可以假設(shè)每個(gè)輸入只對應(yīng)一種答案烦却,且同樣的元素不能被重復(fù)利用宠叼。

示例:

給定 nums = [2, 7, 11, 15], target = 9

因?yàn)?nums[0] + nums[1] = 2 + 7 = 9

所以返回 [0, 1]

(數(shù)組 哈希表)(難度:簡單)

第一次編寫總結(jié) : 這道題考驗(yàn)數(shù)組的處理? 第一次191ms 性能略差? 待優(yōu)化

第一次思路 : 第一次就想到遍歷,想到到類似排序一樣其爵,第一次答的時(shí)候沒太讀懂題意冒冬,以為是一個(gè)數(shù)組中所有等于目標(biāo)(target)的組合,所以就寫的麻煩了一點(diǎn)摩渺,還寫了一個(gè)String數(shù)組轉(zhuǎn)Int數(shù)組简烤,其實(shí)這道題,只輸出一組就可以了

時(shí)間復(fù)雜度 :雙重for循環(huán) n*n = n^2;? 來回轉(zhuǎn)換類型肯定浪費(fèi)時(shí)間摇幻,后面轉(zhuǎn)換的時(shí)候又一次 N級操作? 不過總體來說 算法復(fù)雜度 O(n^2)

? ? public static int[] twoSum(int[] nums, int target) {

? ? ? ? String number = new String();

? ? ? ? for(int i = 0; i <nums.length; i++) {

? ? ? ? ? ? for(int j = i+1;j < nums.length; j++) {

? ? ? ? ? ? ? ? if (nums[i]+ nums[j] == target){

? ? ? ? ? ? ? ? ? number += i + ",";

? ? ? ? ? ? ? ? ? number += j + ",";

? ? ? ? ? ? ? ? }

? ? ? ? ? ? }

? ? ? ? }

? ? ? ? String[] munber = number.split(",");

? ? ? ? int in[] = new int[munber.length];

// 對String數(shù)組進(jìn)行遍歷循環(huán)横侦,并轉(zhuǎn)換成int類型的數(shù)組

? ? ? ? for (int i = 0; i < munber.length; i++) {

? ? ? ? ? ? in[i] = Integer.parseInt(munber[i]);

? ? ? ? }

? ? ? ? return in;

? ? }

Runtime: 191 ms, faster than 1.00% of Java online submissions for Two Sum.

第二次編寫總結(jié) : 明白題后很重要 把第一次代碼進(jìn)行簡化,總體思路還是第一次的 ,總體runtime時(shí)間提升 性能提升百分一百三以上

思路 : 跟第一次一樣 只不過明確返回?cái)?shù)組大小和循環(huán)結(jié)束時(shí)間break

時(shí)間復(fù)雜度 : 依然O(n^2)

public static int[] twoSum(int[] nums, int target) {

? ? int[] number = 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){

? ? ? ? ? ? ? number[0]=i;

? ? ? ? ? ? ? number[1]=j;

? ? ? ? ? ? ? break;

? ? ? ? ? ? }

? ? ? ? }

? ? }

? ? return number;

}

Runtime: 55 ms, faster than 11.33% of Java online submissions for Two Sum.

第三次編寫總結(jié) : 思考去掉沒用的變量創(chuàng)建 增加全局思考 借鑒思想 總體時(shí)間提升一倍左右 相當(dāng)于百分之百

思路 :可以不用創(chuàng)建新變量 可以不用break停止程序 可以直接返回 增加異常拋出

時(shí)間復(fù)雜度 :依然O(n^2)

空間復(fù)雜度 : O(1)

public static int[] twoSum2(int[] nums, int target) {

? ? for(int i = 0; i <nums.length; i++) {

? ? ? ? for(int j = i+1;j < nums.length; j++) {

? ? ? ? ? ? if (nums[j] == target - nums[i]){

? ? ? ? ? ? ? return new int []{i,j};

? ? ? ? ? ? }

? ? ? ? }

? ? }

? ? throw new IllegalArgumentException("no two sum solution");

}

Runtime: 24 ms, faster than 36.77% of Java online submissions for Two Sum.

第四次編寫總結(jié) :這道題 主要考點(diǎn)是數(shù)組和哈希表 我一直沒太理解怎么用到了哈希表绰姻,不過通過我的不懈努力(臭不要臉的借鑒)枉侧,終于懂了

思路? :? 我們的目地是為了讓時(shí)間復(fù)雜度從O(n^2) 加速到 O(n) -> O(logn) 乃至 O(1) ,我們找一個(gè)數(shù)和另一個(gè)數(shù)等于目標(biāo),相當(dāng)于我們有一個(gè)碼要找他的互補(bǔ)的碼狂芋,我們?nèi)绾螐囊粋€(gè)碼找到一個(gè)他的補(bǔ)碼呢榨馁,如果存在補(bǔ)碼,我們需要查找它的索引帜矾。保持?jǐn)?shù)組中每個(gè)元素到索引的映射的最好方法是什么翼虫?哈希表。 而JAVA中什么跟HASH有關(guān)系呢 最常用的是hashmap屡萤,hashmap在不發(fā)生hash碰撞的時(shí)候 時(shí)間復(fù)雜度是O(1) 發(fā)生后 它是一個(gè)鏈表的形式 它的復(fù)雜度也只是O(n)

時(shí)間復(fù)雜度:map讀的地方是O(1)珍剑,但總體還是O(n)

PS :百度百科(我以后也會去看看維基百科的,英語還有待提高) 散列表(Hash table死陆,也叫哈希表)次慢,是根據(jù)關(guān)鍵碼值(Key value)而直接進(jìn)行訪問的數(shù)據(jù)結(jié)構(gòu)。也就是說,它通過把關(guān)鍵碼值映射到表中一個(gè)位置來訪問記錄迫像,以加快查找的速度劈愚。這個(gè)映射函數(shù)叫做散列函數(shù),存放記錄的數(shù)組叫做散列表闻妓。

給定表M菌羽,存在函數(shù)f(key),對任意給定的關(guān)鍵字值key由缆,代入函數(shù)后若能得到包含該關(guān)鍵字的記錄在表中的地址注祖,則稱表M為哈希(Hash)表,函數(shù)f(key)為哈希(Hash) 函數(shù)均唉。

Map<Integer,Integer> mp = new HashMap<>();

for (int i = 0; i < nums.length; i++) {

? ? mp.put(nums[i],i);

}

for (int i = 0; i < nums.length; i++) {

? ? int number = target - nums[i];

? ? if(mp.containsKey(number) && mp.get(number) != i)

? ? ? ? return new int[]{i,mp.get(number)};

}

throw new IllegalArgumentException("no two sum solution");

Runtime: 4 ms, faster than 96.28% of Java online submissions for Two Sum.

第五次編寫總結(jié) : 其實(shí)相當(dāng)于第四次 借鑒的時(shí)候也借鑒了它的優(yōu)化版? 總體提升不大

思路 : 從兩次for循環(huán)中解脫出來是晨,用一個(gè)for循環(huán)實(shí)現(xiàn) 當(dāng)我們迭代元素并將其插入到表中時(shí),我們還會回頭檢查當(dāng)前元素的補(bǔ)碼是否已經(jīng)存在于表中舔箭。如果它存在罩缴,我們已經(jīng)找到它并立即返回。

時(shí)間復(fù)雜度 : 最大的復(fù)雜度還是O(n)

public static int[] twoSum4(int[] nums,int target){

? ? Map<Integer,Integer> mp = new HashMap<>();

? ? for (int i = 0; i < nums.length; i++) {

? ? ? ? int number = target - nums[i];

? ? ? ? if(mp.containsKey(number))

? ? ? ? ? ? return new int[]{mp.get(number),i};

? ? ? ? mp.put(nums[i],i);

? ? }

? ? throw new IllegalArgumentException("no two sum solution");

}

Runtime: 3 ms, faster than 99.85% of Java online submissions for Two Sum.

總結(jié) : 從簡單的數(shù)組操作在到哈希表的應(yīng)用层扶,從性能上看箫章,就可以看出代碼優(yōu)雅的一面,基礎(chǔ)學(xué)習(xí)題也能看出代碼的思考镜会。

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ------WHY 2018.11.21

最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
  • 序言:七十年代末檬寂,一起剝皮案震驚了整個(gè)濱河市,隨后出現(xiàn)的幾起案子戳表,更是在濱河造成了極大的恐慌桶至,老刑警劉巖,帶你破解...
    沈念sama閱讀 222,865評論 6 518
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件匾旭,死亡現(xiàn)場離奇詭異塞茅,居然都是意外死亡,警方通過查閱死者的電腦和手機(jī)季率,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 95,296評論 3 399
  • 文/潘曉璐 我一進(jìn)店門,熙熙樓的掌柜王于貴愁眉苦臉地迎上來描沟,“玉大人飒泻,你說我怎么就攤上這事±袅” “怎么了泞遗?”我有些...
    開封第一講書人閱讀 169,631評論 0 364
  • 文/不壞的土叔 我叫張陵,是天一觀的道長席覆。 經(jīng)常有香客問我史辙,道長,這世上最難降的妖魔是什么? 我笑而不...
    開封第一講書人閱讀 60,199評論 1 300
  • 正文 為了忘掉前任聊倔,我火速辦了婚禮晦毙,結(jié)果婚禮上,老公的妹妹穿的比我還像新娘耙蔑。我一直安慰自己见妒,他們只是感情好,可當(dāng)我...
    茶點(diǎn)故事閱讀 69,196評論 6 398
  • 文/花漫 我一把揭開白布甸陌。 她就那樣靜靜地躺著须揣,像睡著了一般。 火紅的嫁衣襯著肌膚如雪钱豁。 梳的紋絲不亂的頭發(fā)上耻卡,一...
    開封第一講書人閱讀 52,793評論 1 314
  • 那天,我揣著相機(jī)與錄音牲尺,去河邊找鬼卵酪。 笑死,一個(gè)胖子當(dāng)著我的面吹牛秸谢,可吹牛的內(nèi)容都是我干的凛澎。 我是一名探鬼主播,決...
    沈念sama閱讀 41,221評論 3 423
  • 文/蒼蘭香墨 我猛地睜開眼估蹄,長吁一口氣:“原來是場噩夢啊……” “哼塑煎!你這毒婦竟也來了?” 一聲冷哼從身側(cè)響起臭蚁,我...
    開封第一講書人閱讀 40,174評論 0 277
  • 序言:老撾萬榮一對情侶失蹤最铁,失蹤者是張志新(化名)和其女友劉穎,沒想到半個(gè)月后垮兑,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體冷尉,經(jīng)...
    沈念sama閱讀 46,699評論 1 320
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 38,770評論 3 343
  • 正文 我和宋清朗相戀三年系枪,在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了雀哨。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片。...
    茶點(diǎn)故事閱讀 40,918評論 1 353
  • 序言:一個(gè)原本活蹦亂跳的男人離奇死亡私爷,死狀恐怖雾棺,靈堂內(nèi)的尸體忽然破棺而出,到底是詐尸還是另有隱情衬浑,我是刑警寧澤捌浩,帶...
    沈念sama閱讀 36,573評論 5 351
  • 正文 年R本政府宣布,位于F島的核電站工秩,受9級特大地震影響尸饺,放射性物質(zhì)發(fā)生泄漏进统。R本人自食惡果不足惜,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 42,255評論 3 336
  • 文/蒙蒙 一浪听、第九天 我趴在偏房一處隱蔽的房頂上張望螟碎。 院中可真熱鬧,春花似錦馋辈、人聲如沸抚芦。這莊子的主人今日做“春日...
    開封第一講書人閱讀 32,749評論 0 25
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽叉抡。三九已至,卻和暖如春答毫,著一層夾襖步出監(jiān)牢的瞬間褥民,已是汗流浹背。 一陣腳步聲響...
    開封第一講書人閱讀 33,862評論 1 274
  • 我被黑心中介騙來泰國打工洗搂, 沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留消返,地道東北人。 一個(gè)月前我還...
    沈念sama閱讀 49,364評論 3 379
  • 正文 我出身青樓耘拇,卻偏偏與公主長得像撵颊,于是被迫代替她去往敵國和親。 傳聞我的和親對象是個(gè)殘疾皇子惫叛,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 45,926評論 2 361

推薦閱讀更多精彩內(nèi)容