1、Two Sum（两数之和）

Given an array of integers, return indices of the two numbers such that they add up to a specific target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example:

Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

法一：

常规做法，就是可以用两个for循环解决，但是这样的时间复杂度是O(n^2)。

- (NSArray *)twoSumOneWithRandomArr:(NSArray *)randomArr target:(NSInteger)target{
    for (NSInteger i = 0; i < randomArr.count; i++) {
        NSInteger num1 = [randomArr[i] integerValue];
        for (NSInteger j = i +1; j < randomArr.count; j++) {
            NSInteger num2 = [randomArr[j] integerValue];
            if ((num1 + num2) == target) {
                return @[@(i), @(j)];
            }
        }
    }
    return nil;
}

法二：

巧妙做法，空间换时间，一个for循环就能解决，时间复杂度只有O(n)。
一边寻找，一边将之前的值放到字典中，以值为Key，下角标为object。每次判断 target减去一个数的差 为Key，在字典中是否存在。如果存在，说明之前找到过，确实存在在数组中，也就是说有两个数相加等于target。如果不存在，说明没有两个数相加等于target。

- (NSArray *)twoSumOneWithRandomArr:(NSArray *)randomArr target:(NSInteger)target{
    NSMutableDictionary *numAndIndexDict = [NSMutableDictionary new];
    for (NSInteger index = 0; index < randomArr.count; index++) {
        NSNumber *const numOne = randomArr[index];
        NSNumber *const numTwo = @(target - numOne.integerValue);
        NSNumber *const numTwoIndex = numAndIndexDict[numTwo];
        if (numTwoIndex) {
            return @[@(index), numTwoIndex];
        } else {
            numAndIndexDict[numOne] = @(index);
        }
    }
    return nil;
}

python写法：

def twoSum(nums, target):
    """这样写更直观，遍历列表同时查字典"""
    dct = {}
    for i, n in enumerate(nums):
        cp = target - n
        # 如果在字典中存在，说明两个值相加等于target
        if cp in dct:
            return [dct[cp], i]
        else:
            # 以数组中的值为key，角标为value，存储在字典中
            dct[n] = i