1. 两数之和

1. 两数之和 - 力扣（LeetCode）

class Solution {
  std::unordered_map<int, int> Map;
public:
  vector<int> twoSum(vector<int>& nums, int target) {
    for (int i = 0; i < nums.size(); ++i)
      Map[nums[i]] = i + 1;
    for (int i = 0; i < nums.size(); ++i) {
      int ComplementaryIdx = Map[target - nums[i]] - 1;
      if (ComplementaryIdx != i && ComplementaryIdx != -1)
        return {i, ComplementaryIdx};
    }
    std::unreachable();
  }
};

这个解法其实有点死板了，确实可以先扫一遍写成 \(\mathrm O(2n)\)，但其实完全也可以写成 online 的：

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 {};
    }
};

虽然 operator[] 是有副作用的，但该拆成迭代器和 find() 的形式还是得拆，毕竟你看这道题就特别适合这么用。而且拆开来还避免了判断 ComplementaryIdx != i 的这个分支。

二刷

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

没什么好说的。

三刷

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