Leetcode 1. Two Sum 题解

最后编辑于: 2016-03-29

我的解

没想那么多，直接暴力啊。。。

756ms

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

更好的解

有一种说法，叫做 联机算法(Online Algorithm)，时间复杂度 $\mathcal{O}(n)$ ，一切看起来都是那么美好。

只需要对输入的 vector 进行一次遍历就够了，代价是需要维护一个 hash 表，nums[i] 作为 Key，i 作为 Value。把之前遍历过的数存起来，这样我每读一个数，就检查 target - current_num 在不在hash表中，在的话就输出其 Value。

24 ms

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

启发

要逐个遍历判断符合条件与否的时候，用被遍历的元素建立 hash 表，把结果作为条件（Key），然后到 hash 表里面找。