Two Sum

2019, Sep 14    

Two Sum

这一题怎样用一句话描述

从给定的数组中找出两个不同元素的下标，使得这两个元素的和为目标值。

用到什么算法和什么数据结构

用到了暴力法或哈希算法，用到了数组作为数据结构。

  1. 很容易想到 O(n2) 时间复杂度的算法：用两个循环，遍历数组内所有可能的亮亮组合，最坏情况下 O(n2) 的时间内就可以找到解。可以很容易给出如下代码片段（注意 j 是从 i+1 开始迭代，这是因为题目要求不能使用同一个元素）：

     class Solution {
 public:
     vector<int> twoSum(vector<int>& nums, int target) {
         vector<int> result;
         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) {
                     result.push_back(i);
                     result.push_back(j);
                     return result;
                 }
             }
         }
         return result;
     }
 };

  2. LeetCode 上大部分的提交，运行时间都低于 100ms，按照上面的 O(n2) 时间提交只能达到 300ms 以内，战胜区区 27.51% 的 cpp coder。那么有没有更优解呢？事实上有，但这种方法不容易想到，它是先对数组进行一轮排序，同时将排序前的数组下标也排序，因此需要两轮排序即 2O(nlogn)。最后通过夹逼的方式找到和为 target 的两个元素：

     class Solution {
 public:
     vector<int> twoSum(vector<int>& nums, int target) {
         vector<int> result;
         size_t n = nums.size();
         vector<size_t> indexes = sort_indexes(nums);
         sort(nums.begin(), nums.end());

         int beg = 0, end = n - 1;
         while (beg != end) {
             if (nums[beg] + nums[end] == target) {
                 result.push_back(indexes[beg]);
                 result.push_back(indexes[end]);
                 return result;
             } else if (nums[beg] + nums[end] > target) {
                 --end;
             } else {
                 ++beg;
             }
         }

         return result;
     }
 private:
     template <typename T>
     vector<size_t> sort_indexes(const vector<T> &v) {
       // initialize original index locations
       vector<size_t> idx(v.size());
       iota(idx.begin(), idx.end(), 0);

       // sort indexes based on comparing values in v
       sort(idx.begin(), idx.end(), [&v](size_t i1, size_t i2) {return v[i1] < v[i2];});

       return idx;
     }
 };

  3. 通过上述算法，尽管要进行两轮排序，但我们已经可以战胜 81.32% 的 cpp coder 了。我们再来看题目的标签：数组，哈希表。那么是否可以通过哈希算法求解此题呢？我们首先想到，能不能把所有的元素都存进一个哈希表里，以元素的值作为 key、下标作为 value。然后我们遍历整个数组，每遍历一个元素，都寻找 target - key 是否存在于哈希表中（只需要 O(1) 的时间复杂度），如果存在即可返回，不存在则继续遍历。而遍历整个数组的时间复杂度为 O(n)，于是我们终于得到了 O(n) 的算法！由于建立哈希表需要 O(n) 时间，遍历又需要 O(n)，因此最终的时间复杂度为 2O(n)：

     class Solution {
 public:
     vector<int> twoSum(vector<int>& nums, int target) {
         vector<int> result;
         size_t n = nums.size();
         map<int, int> value_index;

         for (size_t i = 0; i < n; ++i) {
             value_index[nums[i]] = i;
         }

         for (size_t i = 0; i < n; ++i) {
             if (value_index.find(target - nums[i]) != value_index.end() && i != value_index[target - nums[i]]) {
                 result.push_back(i);
                 result.push_back(value_index[target - nums[i]]);
                 return result;
             }
         }

         return result;
     }
 };

    上述算法有一个巧合的地方是，假如数组里有两个相同的元素，例如数组 [3,3]，我们在构建哈希表的时候，当第二个 3 插入哈希表时，会覆盖第一个 3，但这恰恰是我们想要的！因为第二次遍历数组时，我们是从前往后遍历，当我们遇到第一个 3 时，此时查哈希表正好可以把第二个 3 查出来。如果数组是 [3,3,3] 时也一样，只不过我们无法求出 [1,2] [0,1] 这两组解了，但按照题意，[0,2] 也是正确的。

  4. 此时我们已经战胜了 93.54% 的 cpp coder 了，但其实我们还能将上述方法进行一遍优化！由于构建 map 需要遍历一轮数组，找出两数之和又需要遍历一轮，何不在构建 map 的过程中就完成寻找呢？带着这个思路，我们可以在每次插入元素到 map 之前，先检查一下 target - <元素值>是否存在于 map 中，如果存在，我们便将这两个下标返回（注意返回的顺序），不论是否存在，我们都将当前元素插入 map。于是我们的算法被简化为：

     class Solution {
 public:
     vector<int> twoSum(vector<int>& nums, int target) {
         size_t n = nums.size();
         map<int, int> value_index;

         for (size_t i = 0; i < n; ++i) {
             int complement = target - nums[i];
             if (value_index.find(complement) != value_index.end()) {
                 vector<int> result{value_index[complement], i};
                 return result;
             }
             value_index[nums[i]] = i;
         }

         throw std::invalid_argument("No two sum solution");
     }
 };

    这个算法跟两次遍历的算法有这相似的巧合之处，原因在于，我们是每当插入一个元素之前“后过头来”看已经插入的哈希表中有没有元素，使得可以计算出 target 值。那么对于 [3,3,3] 这个数组，当遍历到第二个 3 时，我们发现第一个 3 已经在哈希表里了，于是我们可以直接输出 [0,1] 这组解。由此可知，一次遍历的算法和两次遍历的算法，在面对相同的输入时事输出的结果是不一致的，这也许会作为扩展考题呢！

  5. 至此，我们已经击败了 98.93% 的 cpp coder。当然，人外有人，上述算法还不够完美，能不能战胜 100% 的 cpp coder 呢？留给大家思考吧！

通过这题学到了什么

  1. 简单题不能简单对待，如果直接套暴力法，会显得很 low。
  2. 巧用哈希表，在还未插入元素到 map 之前先判断已经在 map 里的 key 能不能和当前元素组成两数之和，这样可以避免被下标不同、值相同用例坑到。

可能（已经）遇到的 BUG 有哪些

注意题目的一大坑：不同元素的下标，这句话传递给我们两个信息：

  1. 不能使用同一个元素，例如 target 是 6，数组是 [3,2,4] 时，根据题意我们就不能使用两次元素 3 了。
  2. 第二个信息是返回下标，粗心的同学可能会返回值。
  3. 下标不同、值相同的用例。例如 target 是 6，数组是 [3,3] 时，很容易导致 Wrong Answer。
Twitter Facebook Google+