两数之和

  • 下标从1开始
  • 按顺序返回下标

时间复杂度O(n)
空间复杂度O(n)

  1. class Solution {
  2. public:
  3.     vector<int> twoSum(vector<int>& numbers, int target) {
  4.         // 构建一个map记录每个元素的值和位置
  5.         unordered_map<int, int> mp;
  6.         for (int i = 0; i < numbers.size(); i++) {
  7.             // 遍历数组，不断向map中加入元素，同时判断map中是否已有与当前元素加起来等于目标值的元素
  8.             auto it = mp.find(target - numbers[i]);
  9.             // 如有有则返回两个元素对应的下标
  10.             if (it != mp.end()) {
  11.                 return {it->second+1, i+1};
  12.             }
  13.             mp[numbers[i]] = i;
  14.         }
  15.         // 遍历结束返回空，数组中没有和等于目标值的两个元素
  16.         return {};
  17.     }
  18. };