[LeetCode] 1. Two Sum
풀이1
#include <algorithm>
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
int size = nums.size();
for(int i = 0; i<size;++i){
for(int j = i+1;j<size;++j){
if(nums[i]+nums[j] == target){
return vector<int>{i,j};
}
}
}
return vector<int>{-1,-1};
}
};
풀이2
- 더 빠른 풀이
- 이전에 비슷한 유형의 문제를 풀며 이 방법을 배웠다
종종 사용하게 될 것 같으니 잘 기억해두면 좋을 것 같다
- 원래는 map을 이용해서 풀었었는데, 다른 사람의 풀이를 보고 unordered_map을 사용하는 것이 더 빠르다는 것을 알게 되었다
#include <algorithm>
#include <unordered_map>
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int, int> m;
int size = nums.size();
for(int i = 0; i<size;++i){
int a = nums[i];
if(m.find(a) != m.end()){
return vector<int>{m[a],i};
}
else{
m[target-a] = i;
}
}
return vector<int>{-1, -1};
}
};