题目链接

算法思路

方法1 暴力求解

（最朴素简单，但不推荐使用）
两层循环，穷举所有可能
复杂度
时间：O(n^2)
空间：O(1)

方法2 用空间换时间，使用map，两次遍历即可

map numsMap; // 存放数字-下标
流程：
1）第一次遍历：将每个元素和它的下标存入numsMap中
2）第二次遍历：对于nums[i]，判断numsMap中是否有target-nums[i]这个元素的下标不为i，如果有，就找到了答案，即i和numsMap[target-nums[i]]
复杂度：
时间：O(n)
空间：O(n), 因为map需要存储空间

方法3 针对方法2进行改进，只需要一次遍历就行

（一边找一边存，方法2是先统一存再统一找）
流程：
遍历nums对于nums[i], 看numsMap里是否有target-nums[i]这个元素，如果有 就找到了答案
复杂度：
时间：O(n)
空间：O(n), 因为map需要存储空间

代码

C++代码
这里给出方法2的代码

  1. vector<int> twoSum(vector<int>& nums, int target) {
  2.         /* 算法思路
  3.         方法1 暴力求解（最朴素简单，但不推荐使用）:
  4.         两层循环，穷举所有可能
  5.         复杂度
  6.         时间：O(n^2)
  7.         空间：O(1)
  8.         ****************
  10.         方法2 用空间换时间，使用map，两次遍历即可
  11.         map<int, int> numsMap; // 存放数字-下标
  12.         流程：
  13.         1）第一次遍历：
  14.         将每个元素和它的下标存入numsMap中
  15.         2）第二次遍历：
  16.         对于nums[i]，判断numsMap中是否有target-nums[i]这个元素的下标不为i，如果有，就找到了答         案，即i和numsMap[target-nums[i]]
  18.         复杂度：
  19.         时间：O(n)
  20.         空间：O(n), 因为map需要存储空间
  22.         ****************
  24.         方法3 针对方法2进行改进，只需要一次遍历就行（一边找一边存，方法2是先统一存再统一找）
  25.         流程：
  26.         遍历nums
  27.         对于nums[i], 看numsMap里是否有target-nums[i]这个元素，如果有 就找到了答案
  28.         */
  32.         // 使用方法2
  33.         map<int, int> numsMap;
  34.         vector<int> result;
  35.         for(int i = 0; i < nums.size(); i++){
  36.             numsMap[nums[i]] = i;
  37.         }
  38.         for(int i = 0; i < nums.size(); i++){
  39.             if(numsMap.find(target-nums[i]) != numsMap.end() && numsMap[target-nums[i]] != i){
  40.                 // 找到了
  41.                 result.push_back(i);
  42.                 result.push_back(numsMap[target-nums[i]]);
  43.                 return result;
  44.             }
  45.         }
  46.         return result;
  47.     }