알고리즘/LeetCode
[LeetCode] [easy] Two Sum (brute-force, map)
느스그
2021. 3. 16. 21:38
1. Problem
Given: numbers array and target.
Select two element and sum, if output is target return these index.
2. brute-force
time-complexity of brute-force is O(N^2)
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
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 {i, j};
}
}
}
return {};
}
};
|
cs |
3. Hash Map
time-complexity use of Hash Map is O(N).
if use 'map' then time is O(NlgN), because map is BST.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int, int> m;
for(int i = 0; i < nums.size(); i++)
{
if(m.count(nums[i]))
return {m[nums[i]], i};
m[target-nums[i]] = i;
}
return {};
}
};
|
cs |