OC算法-两数之和

题目

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。

示例:

给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

题解:

1,暴力法
暴力法很简单，遍历每个元素 x，并查找是否存在一个值与 target - x相等的目标元素。

+(NSArray*)violenceTwoSum:(NSArray*)nums target:(int)target{
    for (int i = 0 ; i < nums.count ; i ++) {
        int n = [nums[i] intValue];
        for (int j = i + 1; j< nums.count ; j ++) {
            if ([nums[j] intValue] == target - n) {
                return @[nums[i],nums[j]];
            }
        }
    }
    return nil;
}

2,hashMap
遍历每个元素x,并查找在map中是否有key为x的键值对,如果有则将键值对返回,如果没有,则将target - x最为key,x作为value保存在map中.
简单点理解,就是两个人配对,x先在公告栏map上看有没有找自己的,如果有就建立配对,如果没有就写上目标以及自己的联系方式{target - x:x},当自己的目标查看公告栏时,就可以直接找到自己.

+(NSArray*)hashTwoSum:(NSArray*)nums target:(int)target{
    NSMutableDictionary *map = [[NSMutableDictionary alloc]init];
    for (int i = 0; i < nums.count; i++) {
        NSNumber *n = nums[i];
        if (map[n]) {
            return @[n,map[n]];
        }else{
            NSNumber *m = @(target - [n intValue]);
            map[m] = n;
        }
    }
    return nil;
}