Two Sum

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。