两数之和

题目：

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

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

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

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

• 自行解答：

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
    vector<int> result ;
    vector<int>::iterator it1 = nums.begin();
    vector<int>::iterator it2 = nums.begin();
    for(;it1!=nums.end();it1++){
        for(it2 = it1+1;it2!=nums.end();it2++){
            if ((*it1) + (*it2) == target){
                int pos1 = distance(nums.begin(), it1);
                int pos2 = distance(nums.begin(), it2);
                result.push_back(pos1);
                result.push_back(pos2);
                return result;
            }
        }
    }
    return result;
    }
};

思路分析解答：

本体暴力解法很简单：直接双层for循环，类似冒泡的思路，挨个对比每一个位置上数字和其他位置的数字相加之和是否为target，即可得到答案。

采用C++实现，可以用到的API 是使用数组vector，采用双迭代器指针迭代，实现每个位置的数字和其他位置数字的相加。

暴力解法时间复杂的为O(N2)，

空间复杂度：O（1）

• 官方分析

  方法1：

  暴力解法，具体参考下面：

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

方法2 ：哈希表法

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

哈希表法采用将数字在数字中位置和值作为key value值存入map中，在采用遍历一次map，将target -key得到结果作为key在次在map中查询，得到即是本题结果。

时间复杂度：O(N),主要作用在遍历map中

空间复杂度：O(N)主要作用在map存储开销上