給定一個數(shù)字數(shù)組 arr, 一個值 sum, 找出數(shù)組中兩個的和為值a的元素 的返回下標 index1, index2(用數(shù)組[index1, index2] 返回, 假設都只有一種答案, 并且數(shù)組中元素不重復)

例如:

arr = [1, 9, 7, 4, 5] sum = 13 返回結(jié)果 [1, 3]

方法一:

思路: 針對于數(shù)組, 循環(huán)處理判斷。 for循環(huán)中套一個for循環(huán), 判斷 "外層元素 == sum -里層元素 "

OC代碼

 NSArray *arr = @[@1, @9, @7, @4, @5];
 int sum = 13;
 NSLog(@"結(jié)果: %@", [self calculate:arr Sum:sum]);

- (NSArray *)calculate:(NSArray *)arr Sum:(int)sum {
    for (int i = 0; i < arr.count; i++) {
        for (int j = i+1; j < arr.count; j++) {
            if ([arr[i] intValue] == (sum - [arr[j] intValue])) {
                return @[[NSNumber numberWithInt:i], [NSNumber numberWithInt:j]];
            }
        }
    }
    return @[];
}

Swift代碼

        let arr = [1, 9, 7, 4, 5], sum = 13
        print("返回結(jié)果: \(self.caculate(arr: arr, sum: sum))")

    func caculate(arr:[Int], sum:Int) -> [Int] {
        for i in 0..<arr.count {
            for j in i+1..<arr.count {
                if arr[i] == sum - arr[j] {
                    return [i, j]
                }
            }
        }
        return [];
    }

不過 雖然節(jié)省執(zhí)行時的內(nèi)存消耗, 但是在時間復雜度方面卻是大大增加成本, 因為兩個遍歷都需要耗時, 效率比較低

方法二:

兩遍哈希表
這邊給小伙伴普及哈希表 什么是哈希表呢?

哈希表是根據(jù)關(guān)鍵碼值(Key value)而直接進行訪問的數(shù)據(jù)結(jié)構(gòu)。也就是說，它通過把關(guān)鍵碼值映射到表中一個位置來訪問記錄，以加快查找的速度。這個映射函數(shù)叫做散列函數(shù)，存放記錄的數(shù)組叫做散列表。

給定表M，存在函數(shù)f(key)，對任意給定的關(guān)鍵字值key，代入函數(shù)后若能得到包含該關(guān)鍵字的記錄在表中的地址，則稱表M為哈希(Hash）表，函數(shù)f(key)為哈希(Hash) 函數(shù)。 (摘自百度百科 ^_)

OC代碼

- (NSArray *)calculate:(NSArray *)arr Sum:(int)sum {
    
    NSMutableDictionary *dic = [NSMutableDictionary dictionary];
    
    for(int i = 0; i < arr.count; i++){
        [dic setValue: [NSString stringWithFormat:@"%d", i] forKey:
         [NSString stringWithFormat:@"%@",arr[i]]];
    }
    
    for(int j = 0; j < arr.count; j++){
        int cmp = sum - [arr[j] intValue];
        NSString *comp = [NSString stringWithFormat:@"%d", cmp];
        if ([dic.allKeys containsObject: dic[comp]] && j != [dic[comp] intValue]) {
            return @[[NSNumber numberWithInt:j],  [NSNumber numberWithInt: [dic[comp] intValue]]];
        }
        
    }
    return @[];
}

Swift代碼

    func caculate(arr:[Int], sum:Int) -> [Int] {
        var dic = [Int:Int]()
        for i in 0..<arr.count {
            dic[arr[i]] = i
        }
        
        for j in 0..<arr.count {
            let cmp:Int = sum - arr[j]
            if(dic.keys.contains(cmp) && dic[cmp] != j){
                if let j1:Int = dic[cmp] {
                    return [j, j1]
                }
            }
        }
        return [];
    }

這種方法時間復雜度雖然節(jié)省, 但是空間復雜度會增加。 為何呢? 因為其實我們可以看出, 很大程度取決于dic能儲存的元素個數(shù)

當然我們可以簡化上面代碼, 減少一次遍歷, 一遍哈希就可以, 這里我只寫swift的了哈

    func caculate(arr:[Int], sum:Int) -> [Int] {
        var dic = [Int:Int]()
        for j in 0..<arr.count {
            let cmp:Int = sum - arr[j]
            if dic.keys.contains(cmp) {
                if let j1:Int = dic[cmp] {
                    return [j, j1]
                }
            }
            dic[arr[j]] = j
        }
        return [];
    }

題目來源：力扣（LeetCode） 感謝力扣爸爸 :)

IOS 算法合集地址