不積硅步無(wú)以至千里
leetcode題庫(kù)第一題——兩數(shù)之和
給定一個(gè)整數(shù)數(shù)組和一個(gè)整數(shù)目標(biāo)值凉蜂，返回兩個(gè)數(shù)的下標(biāo)膨更，這兩個(gè)數(shù)相加和為目標(biāo)值着裹。
條件1：假定給定的數(shù)組中最多有一組數(shù)據(jù)滿(mǎn)足條件幢尚。
條件2: 數(shù)組中的元素每個(gè)只能使用一次茫负。
條件3: 可以以任意順序返回兩個(gè)元素的下標(biāo)蕉鸳。
暫時(shí)有兩種解決辦法：
一、省時(shí)間
解決思路： 先從頭到尾遍歷數(shù)組忍法，取到第一個(gè)元素之后遍歷第一個(gè)元素之后的元素潮尝，然后判斷兩數(shù)之和是否為target，如果找到了饿序，就保存這兩個(gè)數(shù)的下標(biāo)勉失，返回結(jié)果，如果沒(méi)有找到原探，就繼續(xù)查找下一個(gè)元素乱凿，再進(jìn)行判斷，如果都遍歷完了還沒(méi)有找到和為target的值咽弦，就返回{-1,-1}徒蟆。
時(shí)間復(fù)雜度 o(n2)，空間復(fù)雜度o(n),
/**
* @param target 目標(biāo)和
* @param orgArray 找查找的數(shù)組
* @return 符合條件的下標(biāo)
*/
public int[] searchNum(int target, int[] orgArray) {
int[] result = {-1, -1};
for (int i = 0; i < orgArray.length; i++) {
for (int j = i + 1; j < orgArray.length; j++) {
if (orgArray[i] + orgArray[j] == target) {
result[0] = i;
result[1] = j;
return result;
}
}
}
return result;
}
二型型、省空間
解決思路：用一個(gè)hashMap來(lái)存儲(chǔ)整數(shù)數(shù)組的元素和對(duì)應(yīng)的下標(biāo)（key存儲(chǔ)元素段审，value存儲(chǔ)元素對(duì)應(yīng)的下標(biāo)），然后遍歷數(shù)組闹蒜，判斷map中是否存在target - orgArray[i]這樣的key寺枉，如果存在抑淫，就返回map中對(duì)應(yīng)key 的value（對(duì)應(yīng)元素的下標(biāo)）和i。
如果我自己寫(xiě)型凳，可能會(huì)遍歷兩次丈冬，第一次遍歷構(gòu)造map，第二次遍歷判斷甘畅。官方解法中把兩次判斷和在一起同樣可以實(shí)現(xiàn)埂蕊，節(jié)省了代碼的行數(shù)。在以后要寫(xiě)兩次遍歷的時(shí)候疏唾，可以考慮一下是不是可以用一次遍歷實(shí)現(xiàn)蓄氧。
如果想要節(jié)省數(shù)組查找的時(shí)間，可以考慮用HashMap來(lái)實(shí)現(xiàn)槐脏。
時(shí)間復(fù)雜度：o(n)
空間復(fù)雜度：o(n)
/**
* 通過(guò)hash表來(lái)實(shí)現(xiàn)
*
* @param target
* @param orgArray
* @return
*/
public int[] searchNum2(int target, int[] orgArray) {
HashMap hashmap = new HashMap<Integer, Integer>();
for (int i = 0; i < orgArray.length; i++) {
if (hashmap.containsKey(target - orgArray[i])) {
return new int[]{(int) hashmap.get(target-orgArray[i]), i};
}
hashmap.put(orgArray[i], i);
}
return new int[0];
}
