小小程序員的我準(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
