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；
想到这里，第二个解决方案就出炉了：
- 将数组转化成一个map，其中键为数组中的数，值为该数对应得索引值；
- 对于数组（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 存储数据），忍不住的想要多看几遍这优美的代码；
突然，优秀的程序猿发现了在上面的解法中存在两个问题，
- 在查找每个数的补集是否存在的时候面向的是整个map，虽然对于 hashmap 来说这不太影响性能，但是也多了一项判断补集不是其本身啊！！！
- 算法中先实现了将数据填充至map，然后再逐一查询，那么时间复杂度是O(2n)，虽然O(n)和O(2n)是基本一样的，但是能不能再优化一下呢？可以做到边填充边搜索吗？？？
优秀的程序猿不容许这样的瑕疵存在，经过短暂的思考，又一个思路浮现了出来：
- 创建一个空 map；
- 对于数组（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
优秀的程序猿又严谨得审视了几遍代码，满意得合上了电脑。。。
