IOS 算法(基础篇) ----- 两数之和求解问题

给定一个数字数组 arr, 一个值 sum, 找出数组中两个的和为值a的元素的返回下标 index1, index2(用数组[index1, index2] 返回, 假设都只有一种答案, 并且数组中元素不重复)

例如:

arr = [1, 9, 7, 4, 5] sum = 13 返回结果 [1, 3]

方法一:

思路: 针对于数组, 循环处理判断。 for循环中套一个for循环, 判断 "外层元素 == sum -里层元素 "

OC代码

 NSArray *arr = @[@1, @9, @7, @4, @5];
 int sum = 13;
 NSLog(@"结果: %@", [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("返回结果: \(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 [];
    }

不过虽然节省执行时的内存消耗, 但是在时间复杂度方面却是大大增加成本, 因为两个遍历都需要耗时, 效率比较低

方法二:

两遍哈希表
这边给小伙伴普及哈希表什么是哈希表呢?

哈希表是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。

给定表M，存在函数f(key)，对任意给定的关键字值key，代入函数后若能得到包含该关键字的记录在表中的地址，则称表M为哈希(Hash）表，函数f(key)为哈希(Hash) 函数。 (摘自百度百科 ^_)

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 [];
    }

这种方法时间复杂度虽然节省, 但是空间复杂度会增加。为何呢? 因为其实我们可以看出, 很大程度取决于dic能储存的元素个数

当然我们可以简化上面代码, 减少一次遍历, 一遍哈希就可以, 这里我只写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 算法合集地址

最后编辑于：2022.01.21 14:20:26