数组中的两数之和为指定的值，求此两数的索引

2019-02-21

题目

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

你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。

示例：

1
2
3

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

解法1：暴力法

依次遍历数组中的每个数据，查看与数组中的其他数据之和是否为指定的值。

NSArray<NSNumber *> *getSumIndex1(NSArray<NSNumber *> *nums, NSInteger target) {
    // 注意：标准解法需要双重遍历原数组确定索引，时间复杂度为O(n^2)，这里使用NSArray的API进行了简化
    NSArray *sumIndexInfo;
    for (NSNumber *item in nums) {
        // 当前索引
        NSInteger currentIndex = [nums indexOfObject:item];
        // 获取差值
        NSNumber *result = @(target - item.integerValue);
        // 查看是否在数组中
        NSInteger resultIndex = [nums indexOfObject:result];
        if ((resultIndex != NSNotFound)
            && (resultIndex != currentIndex)) {
            // 找到，得到索引并返回
            sumIndexInfo = @[@(currentIndex), @(resultIndex)];
            break;
        }
    }
    return sumIndexInfo;
}

解法2：两次遍历哈希表

这里使用了NSDictionary类进行实现，目的是为了快速查找到数据对应的索引：

NSArray<NSNumber *> *getSumIndex2(NSArray<NSNumber *> *nums, NSInteger target) {
    // 使用哈希表进行存取，加快查找速度
    NSMutableDictionary *hashTable = [@{} mutableCopy];
    for (NSInteger index = 0; index < nums.count; index++) {
        // key为数据值，value为索引（目的为了快速通过数值查询到索引）
        [hashTable setObject:@(index) forKey:nums[index]];
    }
    NSArray *sumIndexInfo;
    for (NSInteger index = 0; index < nums.count; index++) {
        NSInteger currentValue = [nums[index] integerValue];
        // 获取差值
        NSNumber *result = @(target - currentValue);
        // 在哈希表中查找对应索引
        NSNumber *resultIndex = [hashTable objectForKey:result];
        if ((resultIndex)
            && (resultIndex.integerValue != index)) {
            sumIndexInfo = @[@(index), resultIndex];
            break;
        }
    }
    return sumIndexInfo;
}

解法3：一次遍历哈希表

遍历插入哈希表的同时，直接在表中查询，符合直接返回。

NSArray<NSNumber *> *getSumIndex3(NSArray<NSNumber *> *nums, NSInteger target) {
    // 简化了方法2，一次遍历同时直接查询
    
    NSArray *sumIndexInfo;
    // 使用哈希表进行存取，加快查找速度
    NSMutableDictionary *hashTable = [@{} mutableCopy];
    for (NSInteger index = 0; index < nums.count; index++) {
        NSNumber *currentItem = nums[index];
        // 获取差值
        NSNumber *result = @(target - currentItem.integerValue);
        // 直接查询当前哈希表中是否已经包含差值对象
        NSNumber *resultIndex = [hashTable objectForKey:result];
        if ((resultIndex)
            && (resultIndex.integerValue != index)) {
            sumIndexInfo = @[@(index), resultIndex];
            break;
        } else {
            // key为数据值，value为索引（目的为了快速通过数值查询到索引）
            [hashTable setObject:@(index) forKey:currentItem];
        }
    }
    return sumIndexInfo;
}

由于在OC的数组中已经包含了根据元素直接返回索引的高级API，故大幅度简化了解法1，使用哈希表快速返回索引也变得没有那么必要了。