题目
给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。
- 示例：
给定 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，使用哈希表快速返回索引也变得没有那么必要了。
