- 注：之前在其他平臺的文章與記錄慢慢也都放這邊吧赋访，權(quán)當(dāng)資料遷移與備份可都。如下：
LeetCode，最近才知道有這么好的平臺可以刷題蚓耽，真是慚愧慚愧∏現(xiàn)在開始，努力步悠，一道道地刷題签杈！剛開始，難免有不足的地方鼎兽。也有借用別人思路的部分答姥，學(xué)習(xí)才能進(jìn)步！之前想一道道地刷谚咬，但是能力問題鹦付，又要做其他事，很容易就停下了择卦，今天在豆瓣看到一個對題目進(jìn)行分類的敲长，挺不錯，補(bǔ)充mark一下：LeetCode 題目總結(jié)/分類
一秉继、題
第一道題Two Sum 如下：
- Given an array of integers, find two numbers such that they add up to a specific target number.
- The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.
- You may assume that each input would have exactly one solution.
Input: numbers={2, 7, 11, 15}, target=9 Output: index1=1, index2=2
簡單來說祈噪，就是給一數(shù)組及一數(shù)值，求數(shù)組中兩元素相加為該數(shù)值對應(yīng)的兩個索引尚辑。且要求index1小于index2辑鲤，而且答案結(jié)果穩(wěn)定。
二杠茬、解：
2.1 遍歷：
最粗暴的方法月褥，時間復(fù)雜度為O(n^2)。一開始提交通不過澈蝙，太耗時了吓坚，后來又可以提交。略奇怪灯荧。
public class Solution {
public int[] twoSum(int[] nums, int target) {
int index1,index2;
int[] index=new int[]{0,1};
for(int i = 0; i< nums.length; i++)
{
for(int j = i+1; j< nums.length; j++)
{
if(target==(nums[i]+nums[j]))
{
index[0] = i+1;
index[1] = j+1;
return index;
}
}
}
return index;
}
}
2.2 HashSet
利用HashSet元素不能重復(fù)的原理礁击，新建一個HashSet，然后可先檢查target-nums[i]能否加入該HashSet逗载，若能哆窿，則說明前面的數(shù)據(jù)沒有與第i個符合的組合。在把該target-nums[i]刪除厉斟，重新添加nums[i]（避免有兩個元素相等返回錯誤判斷）挚躯。當(dāng)添加不成功，則說明存在符合的組合擦秽，記錄此時的i码荔，并從i以前的數(shù)組尋找他的另一半漩勤。有點繁瑣，但時間復(fù)雜度為O(n)缩搅，空間復(fù)雜度為O(n)越败。
public class Solution {
public int[] twoSum(int[] nums, int target) {
int index1,index2;
int[] index=new int[]{0,1};
Set nset = new HashSet();
for(int i = 0; i< nums.length; i++)
{
if(nset.add(target-nums[i])) //檢查是否有nums[i]配對的元素存在，無則添加成功
{
nset.remove(target-nums[i]); //添加該元素只是為了判斷是否存在硼瓣，本來不應(yīng)該添加的這里又刪掉
nset.add(nums[i]);
}else
{
index[1] = i+1;
for(int j = 0; j< i; j++)
{
if(target==(nums[i]+nums[j]))
{
index[0] = j+1;
return index;
}
}
return index;
}
}
return index;
}
}
有點奇怪究飞，以上提交后的結(jié)果為“Runtime: 332 ms”，但是我把用add()方法來判斷是否存在的方式替換成直接用contains()方法來判斷堂鲤，即把“ if(nset.add(target-nums[i])) ”換成“if(!nset.contains(target-nums[i])) ” 然后刪掉“nset.remove(target-nums[i]); ”亿傅，但是“Runtime: 364 ms”。試了幾次瘟栖，大小有變動葵擎，但是總是后者要耗時多點。但實際是少執(zhí)行一條命令半哟。這里有點疑惑坪蚁。不知是采用黑盒測試來檢驗算法的正確性。
另外镜沽，有人疑慮HashSet在添加元素的時候去判斷是否已存在元素不用去遍歷已有的集合嗎敏晤？這不是跟第一個方法的遍歷一樣嗎？其實不然缅茉，HashSet 的元素存放位置是根據(jù)每個元素的哈希碼來放的嘴脾，就是知道一個元素，算出其哈希碼蔬墩，就能知道他存放的地址译打。就像學(xué)校，每來一個新生就給他個學(xué)號拇颅，老師找你不用一間間宿舍去找你奏司，只要知道學(xué)號就能直接定位到你的宿舍。
2.3 HashMap
用HashMap來做樟插，道理相同韵洋，不過跟二還是有點區(qū)別。1黄锤、HashMap要需要為每個元素創(chuàng)建key和value兩個內(nèi)存空間搪缨，輔助空間翻倍。本例子就是用value來放index鸵熟；2副编、由于用value來放index，找到一個后流强，另外一個就馬上可以得到其index痹届。二跟三呻待，一個省點空間、一個省點點時間队腐，都差別不大带污。
public class Solution {
public int[] twoSum(int[] nums, int target) {
int[] index=new int[]{0,1};
HashMap<Integer,Integer> hm = new HashMap<Integer,Integer>();
for(int i = 0; i<nums.length; i++)
{
if(hm.containsKey(target - nums[i]))
{
index[1] = i+1;
index[0] = hm.get(target-nums[i])+1;
return index;
}else
{
hm.put(nums[i],i);
}
}
return index;
}
}
