Leetcode 1. Two Sum 题解

Last Updated At: 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),时间复杂度 ,一切看起来都是那么美好。

只需要对输入的 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 表里面找。