Two Sum 286ms 2.67%

<-E> Two Sum 286ms 2.67%

vector<int> twoSum(vector<int>& nums, int target) {
    vector <int> answer;
    for (auto i = 0; i != nums.size(); i++) {
        for (auto j = i + 1; j != nums.size(); j++) {
            if (nums[i] + nums[j] == target) {
                answer.push_back(i);
                answer.push_back(j);
            }
        }
    }
    return answer;
}

大佬的解法： 利用hashmap的无序性。 hash.find(numberToFind) != hash.end() 如果没有找到，则将元素的值作为hash的key， 元素的位数为值添加到map中。以此类推直到找到该元素为止。

vector<int> twoSum(vector<int> &numbers, int target) {
    //Key is the number and value is its index in the vector.
    unordered_map<int, int> hash;
    vector<int> result;
    for (int i = 0; i < numbers.size(); i++) {
        int numberToFind = target - numbers[i];
        // if numberToFind is found in map, return them
        if (hash.find(numberToFind) != hash.end()) {
            result.push_back(hash[numberToFind]);
            result.push_back(i);
            return result;
        }
        // number was not found. Put it in the map.
        hash[numbers[i]] = i;
    }
    return result;
}

展开

使用unordered_map来做。 该数据结构被定义在unordered_map 库中。

• unordered_map 内部实现为哈希表。（所以是无序的）
• map 内部实现为红黑树（所以map内部的元素都是有序的）

map

优点：

• 有序性
• 内部由红黑树实现（使用红黑树特性的时候，效率快）

缺点：

• 空间占用率高（节点）

unordered_map

优点：

• 查找快

缺点：

• 建立hash表的时候，消耗大量时间