題目：
給定一個(gè)整數(shù)數(shù)組 nums 和一個(gè)目標(biāo)值 target茸习，請(qǐng)你在該數(shù)組中找出和為目標(biāo)值的那 兩個(gè) 整數(shù)，并返回他們的數(shù)組下標(biāo)壁肋。
你可以假設(shè)每種輸入只會(huì)對(duì)應(yīng)一個(gè)答案自沧。但是科阎，數(shù)組中同一個(gè)元素不能使用兩遍。
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/two-sum
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系官方授權(quán)末患，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。
考察點(diǎn)：
- 這是一道LeetCode上非称嗣模基礎(chǔ)的一道算法題俏拱。主要考察的就是哈希表查找對(duì)應(yīng)鍵值的時(shí)間復(fù)雜度O(1)。
解法：
一察净、暴力循環(huán)
- 循環(huán)數(shù)組中每一個(gè)數(shù)字和之后的數(shù)字做比較驾茴，若兩者和為目標(biāo)數(shù)值return兩個(gè)數(shù)字的index
- 時(shí)間復(fù)雜度O(n2)
- (NSArray *)twoSums:(NSArray <NSNumber *>*)numArray equalTo: (int) total {
for (int i = 0; i < numArray.count; i++) {
for (int j = i + 1; j < numArray.count; j++) {
int q = [numArray[i] intValue];
int w = [numArray[j] intValue];
if(q + w == total) {
return @[@(i), @(j)];
}
}
}
return nil;
}
二、使用哈希表
- 在循環(huán)數(shù)組將值插入表中的同時(shí)氢卡，查找哈希表中是否含有目標(biāo)值減去當(dāng)前值的key锈至。如果存在將其立即返回
- 時(shí)間復(fù)雜度：O(n)，因?yàn)槲覀冎槐闅v了包含有 n 個(gè)元素的列表一次译秦。在表中進(jìn)行的每次查找只花費(fèi) O(1) 的時(shí)間峡捡。這樣就降低了算法的時(shí)間復(fù)雜度
- NSDictionary底層就是哈希表所以這里我們用NSDictionary代替
- (NSArray *)dictTwoSums:(NSArray <NSNumber *>*)numArray equalTo: (int) total {
NSMutableDictionary *usedNums = [NSMutableDictionary dictionaryWithCapacity:numArray.count];
for (int i = 0; i < numArray.count; i++) {
int q = [numArray[i] intValue];
NSNumber *w = [NSNumber numberWithInt:(total - q)];
if([[usedNums allKeys]containsObject:w]) {
return @[@(i), [usedNums objectForKey:w]];
} else {
[usedNums setObject:@(i) forKey:numArray[i]];
}
}
return nil;
}
總結(jié)
- 這道題讓我了解并熟悉了哈希表，理解了這個(gè)算法對(duì)你之后編程的思路的思考有很大幫助
- 如果想要了解更多hash表筑悴、NSDictionary的相關(guān)知識(shí)可以看這篇文章们拙，我覺得寫的還是很不錯(cuò)的
http://www.reibang.com/p/0d7cd6341f65
思考
- 這兩個(gè)算法寫完思路雖然比原來擴(kuò)展了，但這兩個(gè)方法執(zhí)行起來的時(shí)間阁吝，不管數(shù)組長(zhǎng)短砚婆，元素位置變化，總是第一個(gè)方法實(shí)現(xiàn)的時(shí)間更短突勇。背后的原因是因?yàn)镹SDictionary的相關(guān)方法增加了開銷装盯，還是其他原因坷虑，值得思考。
