001.Two Sum[E]

1.题目

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

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

示例 1：

输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

示例 2：

输入：nums = [3,2,4], target = 6
输出：[1,2]

示例 3：

输入：nums = [3,3], target = 6
输出：[0,1]

提示：

2 <= nums.length <= 103
-109 <= nums[i] <= 109
-109 <= target <= 109
只会存在一个有效答案

2.思路

作为我们可能进入leetcode遇到的第一题，大家对它可谓是又爱又恨，而且它确实又有很多解法，总结起来可以有以下3种，3种还都能A过….

2.1 双重循环

最简单的思路，两重循环，没啥技术含量，速度很慢，毕竟是$O(N^2)$

Java写法

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> result;
        for(int i = 0;i < nums.size();i++)
        {
            for(int j = i+1;j < nums.size();j++)
                if(nums[i] + nums[j] == target)
                {
                    result.push_back(i);
                    result.push_back(j);
                    return result;
                }

        }
    }
};

JS写法（后续我都会用JS的方式写）

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(nums, target) {
    for (let i = 0, len = nums.length;i < len; i++) {
      for (let j = i; j < len; j++) {
        if(nums[i] + nums[j] === target) {
          return [i, j]
      }
    }
  }
};

2.2 排序（双指针）

其实简单的想，用一个排序都能把复杂度降到 O(NlogN，通过排序，然后用两个指针从前后扫描逼近真值(注意这个思想，可以让O(N*N)的复杂度降为O(N),充分利用排序，因为一定会有一个值满足，然后通过值去原数组里找对应的下标（这里其实就可以考虑，如果当初就用一个数据结构存好键值对应关系就好了，其实就是 hashmap，下面的做法就用到了）
（下面代码是 dugu9sword写的java代码，我就没写成c++的，主要看思路，还是比较好理解的）

public class Solution {
    public int[] twoSum(int[] nums, int target) {
        int[] nums_sorted=new int[nums.length];
        System.arraycopy(nums,0,nums_sorted,0,nums.length);
        //Quicksort.
        Arrays.sort(nums_sorted);

        //Find the two numbers. O(n)
        int start=0;
        int end=nums_sorted.length;
        while(start<end){
            while(nums_sorted[start]+nums_sorted[--end]>target);
            if(nums_sorted[end]+nums_sorted[start]==target)
                break;
            while(nums_sorted[++start]+nums_sorted[end]<target);
            if(nums_sorted[end]+nums_sorted[start]==target)
                break;
        }

        //find the indices of the two numbers
        int[] ret=new int[2];
        int index=0;
        int a=nums_sorted[start];
        int b=nums_sorted[end];
        for(int i=0;i<nums.length;i++)
            if(nums[i]==a || nums[i]==b)
                ret[index++]=i;
        return ret;
    }
}

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
 const sortFn = (v1, v2) => Number(v1) - Number(v2);

 const findFn = target => v => v === target; 

 var twoSum = function(nums, target) {
     // 排序
   let newNums = [...nums].sort(sortFn);
   let front = 0, tail = newNums.length - 1;
   // 指针front 和 tail 分别从头尾开始遍历
   while(front < tail){
       const total = newNums[front] + newNums[tail];
     if (total === target) {
         break;
     }
     if (total < target) {
       // front移动，和增大
         front ++;
     } else {
       // tail移动，和减小
         tail--;
     }
   }
   // 查询对应原数组的下标
   return [nums.indexOf(newNums[front]), nums.lastIndexOf(newNums[tail])];
 };

几个坑需要注意一下：

数组中可能有相同的元素，例如下面案例
```
[1, 1], 2
```
在根据值查询原数组中的位置的时候，自己使用数组查找会没有这个问题，但是在使用已有的元素查找方法的时候要特别注意（indexOf就不行，需要一个使用indexOf，一个使用lastIndexOf)

2.3 Hashmap

最后一种是比较聪明的做法，用hashmap，hashmap是内部存储方式为哈希表的map结构，哈希表可以达到查找O(1)，哈希表的介绍可以看这里, C++实现Hashmap的方式，这里用unordered_map关联容器，可以实现键值对应。

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> result;
        unordered_map<int,int> mymap;
        int res;
        for(int i = 0;i < nums.size();i++)
        {
            res = target - nums[i];
            unordered_map<int,int>::iterator it = mymap.find(res);
            if(it != mymap.end())
            {
                return vector<int>({it->second,i});
            }
            mymap[nums[i]] = i;
        }
    }
};

我们在Map中存储的key是值，value是相应值对应的下标。这样，我们每次循环只用看target - nums[i]的值在不在Map中就行了。

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */ 
 var twoSum = function(nums, target) {
   const map = new Map();
   for (let i = 0, len = nums.length; i < len; i++) {
       const res = target - nums[i];
     if (map.has(res)) {
         return [map.get(res), i];
     }
     map.set(nums[i], i);
   }
   return [];
 };

LeetBook