优秀的程序猿解题之LeetCode 第一题：Two Sum

Tips:所有代码实现包含三种语言（java、c++、python3）

题目

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.

给定数组，返回数组中相加等于给定数的两个数的位置。

可假设仅有一个解，注意数组中的每个数仅可使用一次。

样例

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

解题

首先看到：

输入：一个数组（nums）和一个数（target）；

输出：由数组（nums）的两个索引组成的新数组，其中这两个索引对应的数满足相加等于数（target）；

​

优秀的程序猿很快理解了问题，然后迅速的把问题转化成计算机好理解的问题：

对于数组（nums）中每个数（temp），求数组中是否存在数x（x满足x = target - temp)；

不假思索，优秀的程序猿瞬间想到了暴力遍历法：

对数组每个数，遍历查找数组中此数之后的数是否存在此数的补集。

注意：当我们找到一个解之后就可以立即返回了，因为题目中提到了可假设仅有一个解。

// java
/* 
Runtime: 20 ms, faster than 41.25% of Java online submissions for Two Sum.
Memory Usage: 38.5 MB, less than 44.37% of Java online submissions for Two Sum.
*/
public int[] twoSum(int[] nums, int target){
    int length = nums.length;
    for (int i = 0; i < length - 1; i++){
        for (int j = i + 1; j < length; j++){
            if (nums[i] + nums[j] == target){
                return new int[]{i, j};
            }
        }
    }
    return null;
}

// c++
/*
Runtime: 136 ms, faster than 36.44% of C++ online submissions for Two Sum.
Memory Usage: 9.5 MB, less than 79.36% of C++ online submissions for Two Sum.
*/
vector<int> twoSum(vector<int>& nums, int target) {
    for(int i = 0; i < nums.size()-1; i++)
    {
        for(int j = i+1; j < nums.size(); j++)
        {
            if(nums[i] + nums[j] == target){
                return {i, j};
            }
        }
    }
    return {};
}

# python3
# Runtime: 5528 ms, faster than 11.87% of Python3 online submissions for Two Sum.
# Memory Usage: 13.5 MB, less than 49.67% of Python3 online submissions for Two Sum.
def twoSum(self, nums: List[int], target: int) -> List[int]:
    for i in range(len(nums)-1):
        for j in range(i+1, len(nums)):
            if nums[i] + nums[j] == target:
                return [i,j]
    return None

不幸的是，可以看到，这个方法的表现比较差，仅 Runtime 来说，处理中下游，优秀的程序猿当然不仅满足于此；

优秀的程序猿继续思考着优化方案，再看一遍问题：

对于数组（nums）中每个数（temp），求数组中是否存在数x（x满足x = target - temp)；

优秀的程序猿此时敏感得发现这其中包含一个非有序查找问题，对于非有序查找问题的立马联想到了map；

想到这里，第二个解决方案就出炉了：

1. 将数组转化成一个map，其中键为数组中的数，值为该数对应得索引值；
2. 对于数组（nums）中每个数（temp），查找map中是否存在等于（target-temp）的键，如果存在，返回该键对应的值以及当前数的索引值；

注意：如果当前数等于target的一半，那么当前数的补集就是其本身，因为题目要求数组中的每个数仅可使用一次，此时需判断当前数的补集不是其本身。

// java
/*
Runtime: 3 ms, faster than 99.77% of Java online submissions for Two Sum.
Memory Usage: 39.9 MB, less than 5.16% of Java online submissions for Two Sum.
*/
public int[] twoSum(int[] nums, int target){
    int length = nums.length;
    Map<Integer, Integer> numsMap = new HashMap<>();
    for (int i = 0; i < length; i++){
        numsMap.put(nums[i], i);
    }
    for (int i = 0; i< length; i++){
        int complement = target - nums[i];
        if (numsMap.containsKey(complement) && numsMap.get(complement) != i){
            return new int[]{i, numsMap.get(complement)};
        }
    }
    return null;
}

// c++
/*
Runtime: 12 ms, faster than 97.81% of C++ online submissions for Two Sum.
Memory Usage: 10.6 MB, less than 12.73% of C++ online submissions for Two Sum.
*/
vector<int> twoSum(vector<int>& nums, int target) {
    unordered_map<int, int> numsMap; 
    for(int i = 0; i < nums.size(); i++)
    {
        numsMap[nums[i]] = i;
    }
    for(int i = 0; i < nums.size(); i++)
    {
        if(numsMap.count(target-nums[i]) && numsMap[target-nums[i]] != i){
            return {numsMap[target-nums[i]], i};
        }
    }
    return {};
}

# python3
# Runtime: 40 ms, faster than 73.58% of Python3 online submissions for Two Sum.
# Memory Usage: 15.2 MB, less than 5.08% of Python3 online submissions for Two Sum.
def twoSum(self, nums: List[int], target: int) -> List[int]:
    nums_dict = {}
    for i, num in enumerate(nums):
        nums_dict[num] = i
    for i, num in enumerate(nums):
        if (target-num) in nums_dict and i != nums_dict[target-num]:
             return [i, nums_dict[target-num]]
    return None

不愧是一个优秀的程序猿，这个Runtime表现让我们很是欣慰（Memory Usage 很大是因为我们使用了额外的map 存储数据），忍不住的想要多看几遍这优美的代码；

突然，优秀的程序猿发现了在上面的解法中存在两个问题，

1. 在查找每个数的补集是否存在的时候面向的是整个map，虽然对于 hashmap 来说这不太影响性能，但是也多了一项判断补集不是其本身啊！！！
2. 算法中先实现了将数据填充至map，然后再逐一查询，那么时间复杂度是O(2n)，虽然O(n)和O(2n)是基本一样的，但是能不能再优化一下呢？可以做到边填充边搜索吗？？？

优秀的程序猿不容许这样的瑕疵存在，经过短暂的思考，又一个思路浮现了出来：

1. 创建一个空 map；
2. 对于数组（nums）中每个数（temp），查找map中是否存在等于（target-temp）的键，如果存在，返回该键对应的值以及当前数的索引值；如果不存在，将该数作为键，其索引作为值，放入map中；

在这个思路中，相当于对于数组中的每个数，其补集的搜索范围是数组中位于此数之前的数，即做到了边填充边搜索，又避免了搜索范围的浪费。

// java
/*
Runtime: 3 ms, faster than 99.77% of Java online submissions for Two Sum.
Memory Usage: 38.7 MB, less than 36.97% of Java online submissions for Two Sum.
*/
public int[] twoSum(int[] nums, int target){
    int length = nums.length;
    Map<Integer, Integer> numsMap = new HashMap<>();
    for (int i = 0; i < length; i++) {
        int complement = target - nums[i];
        if (numsMap.containsKey(complement)){
            return new int[]{i, numsMap.get(complement)};
        }
        numsMap.put(nums[i], i);
    }
    return null;
}

// c++
/*
Runtime: 12 ms, faster than 97.81% of C++ online submissions for Two Sum.
Memory Usage: 10.5 MB, less than 21.80% of C++ online submissions for Two Sum.
*/
vector<int> twoSum(vector<int>& nums, int target) {
    unordered_map<int, int> numsMap; 
    for(int i = 0; i < nums.size(); i++)
    {
        if(numsMap.count(target-nums[i])){
            return {numsMap[target-nums[i]], i};
        }
        numsMap[nums[i]] = i;
    }
    return {};
}

# python3
# Runtime: 40 ms, faster than 73.58% of Python3 online submissions for Two Sum.
# Memory Usage: 14.4 MB, less than 5.08% of Python3 online submissions for Two Sum.
def twoSum(self, nums: List[int], target: int) -> List[int]:
    nums_dict = {}
    for i, num in enumerate(nums):
        if (target-num) in nums_dict:
            return [nums_dict[target-num], i]
        nums_dict[num] = i
    return None

优秀的程序猿又严谨得审视了几遍代码，满意得合上了电脑。。。