Input
vector<int>& nums
int target
Output
vector<int>
제한사항
2 <= nums.length <= 105
-109 <= nums[i] <= 109
-109 <= target <= 109
Only one valid answer exists
vector<int> answer;
- 모든 nums를 돌면서 nums[i] + nums[j] == target일때 answer에 i, j를 저장하고 break
- return answer;
- map<int, int> m : m[숫자] = 위치
- for문을 통해 nums의 모든 요소들을 m에 추가 시키고 만약 중복되는 값이 있다면 해당값*2 == target인지 확인하고 answer에 값 추가
- 나머지는 nums를 돌면서 (target - nums[i]) 가 존재하는지 확인하면서 존재할때 해당 위치들을 answer에 추가
- O(n^2)
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
vector<int> answer;
for(int i = 0; i < nums.size() - 1; i++) {
for(int j = i + 1; j < nums.size(); j++) {
if(nums[i] + nums [j] == target) {
answer.push_back(i);
answer.push_back(j);
break;
}
}
}
return answer;
}
};
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
vector<int> answer;
map<int, int> m;
for(int i = 0; i < nums.size(); i++) {
if(m[nums[i]]) {
if(nums[i] * 2 == target) {
answer.push_back(m[nums[i]]);
answer.push_back(i);
break;
}
else continue;
}
m[nums[i]] = i;
}
if(!answer.empty()) return answer;
for(int i = 0; nums[i] <= target; i++) {
if(m[target-nums[i]]) {
answer.push_back(m[nums[i]]);
answer.push_back(m[target-nums[i]]);
break;
}
}
return answer;
}
};
Input: nums = [3,3] | target = 6 | Output: [0,1]
같은 숫자가 등장할 때의 if문이 작동x,
앞 숫자의 위치가 0이기에 작동 x
- map에 저장하는 (위치)를 (위치+1)로 저장하여 if문에 걸리지 않게함.
- 나중에 answer에 추가할때 (값-1)으로 바꿔준다.
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
vector<int> answer;
map<int, int> m;
for(int i = 0; i < nums.size(); i++) {
if(m[nums[i]]) {
if(nums[i] * 2 == target) {
answer.push_back(m[nums[i]] - 1);
answer.push_back(i);
return answer;
}
else continue;
}
m[nums[i]] = i + 1;
}
for(int i = 0; nums[i] <= target; i++) {
if(m[target-nums[i]]) {
answer.push_back(m[nums[i]] - 1);
answer.push_back(m[target-nums[i]] - 1);
break;
}
}
return answer;
}
};
Input: nums = [3,2,4] | target = 6 | Output: [1,2]
3이 하나밖에 없기 때문에 6-3=3인 경우를 예외로 처리해줘야한다.
- if(target-nums[i] == nums[i]) continue; 를 추가해 해당 경우를 건너뛰게 한다.
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
vector<int> answer;
map<int, int> m;
for(int i = 0; i < nums.size(); i++) {
if(m[nums[i]]) {
if(nums[i] * 2 == target) {
answer.push_back(m[nums[i]] - 1);
answer.push_back(i);
return answer;
}
else continue;
}
m[nums[i]] = i + 1;
}
for(int i = 0; i < nums.size(); i++) {
if(m[target-nums[i]]) {
if(target-nums[i] == nums[i]) continue;
answer.push_back(m[nums[i]] - 1);
answer.push_back(m[target-nums[i]] - 1);
break;
}
}
return answer;
}
};
1) 평가
2) 속도&메모리