LeetCode - Two Sum

三种解法

暴力解法

Brute Force

遍历vector, 对每个元素: 从后继找出二者之和满足条件者

1. 使用n保存vector大小
   
2. i的上限为 n - 2 , j的上限为 n - 1
   

Copy 1class Solution {
 2public:
 3    vector<int> twoSum(vector<int>& nums, int target) {
 4        int n = nums.size();
 5        for (int i = 0; i < n - 1; ++i)
 6        {
 7            for (int j = i + 1; j < n; ++j)
 8            {
 9                if (nums[i] + nums[j] == target)
10                {
11                    return {i, j};
12                }
13            }
14        }
15        return {-1, -1};
16    }
17};

优化

暴力解法的时间复杂度为O(n²), 一个容易想到的优化, 数组中是否存在值为 target - nums[i] 的元素

1. 关联容器中提供find和count函数判断元素是否存在于集合中
   
2. 使用map, 可以将vector索引用作值, 将vector值用作索引; 索引会重复
   
3. 使用无序关联容器, 可以提高元素查找的效率
   

完整添加一遍

使用unordered_map

1. 集合中可能存在值相等的元素, 使用下标运算符往map中插入键已存在元素时, 覆写该元素的值
   
2. 使用count是为了判断元素存在; 确定集合中存在该元素时, 才用下标运算符查找元素
   
   因为对已出现过元素进行了覆写, map中存在的元素一定时之后位置的
   

Copy 1class Solution {
 2public:
 3    vector<int> twoSum(vector<int>& nums, int target) {
 4        unordered_map<int, int> tm;
 5        auto n = nums.size();
 6        for (auto i = 0; i < n; ++i)
 7        {
 8            tm[nums[i]] = i;
 9        }
10
11        for (auto i = 0; i < n; ++i)
12        {
13            auto temp = target - nums[i];
14
15            if (tm.count(temp) && tm[temp] != i)
16            {
17                return vector<int> {i, f->second};
18            }
19        }
20        return vector<int> {-1, -1};
21    }
22};

使用unordered_multimap

不推荐

Copy 1class Solution {
 2public:
 3    vector<int> twoSum(vector<int>& nums, int target) {
 4        unordered_multimap<int, int> tm;
 5        auto n = nums.size();
 6        for (auto i = 0; i < n; ++i)
 7        {
 8            tm.insert(pair<int, int>(nums[i], i));
 9        }
10
11        for (auto i = 0; i < n; ++i)
12        {
13            auto temp = target - nums[i];
14
15            auto f = tm.find(temp);
16            if (f != tm.end())
17            {
18                if (f->second != i)
19                {
20                    return vector<int> {i, f->second};
21                }
22                else
23                {
24                    auto cnt = tm.count(temp);
25                    if (cnt == 1)
26                    {
27                        continue;
28                    }
29                    else
30                    {
31                        return vector<int> {i, (++f)->second};
32                    }
33                }
34            }
35        }
36        return vector<int> {-1, -1};
37    }
38};

边添加边判断

Copy 1class Solution {
 2public:
 3    vector<int> twoSum(vector<int>& nums, int target) {
 4        unordered_map<int, int> tm;
 5        auto n = nums.size();
 6        for (auto i = 0; i < n; ++i)
 7        {
 8            auto temp = target - nums[i];
 9            if (tm.count(temp))
10            {
11                return vector<int> {nums[temp], i};
12            }
13            tm[nums[i]] = i;
14        }
15        return vector<int> {-1, -1};
16    }
17};