https://leetcode.com/problems/3sum/
풀이
nums[i] + nums[j] + nums[k] = 0을 만족하는 i, j, k를 찾는 문제이다.
여러 가지 풀이 방법이 있는 2 sum을 n번 돌리면 되는 것 같아 보이지만 output이 중복을 제거한 정답들의 리스트라는 점에서 제약이 생긴다.
먼저 nums를 정렬을 하고 i < j < k 인 순서대로 답을 찾아보자. j = i+1, k = nums.size()-1로 두 개의 포인터를 초기화를 한 후 아래 조건대로 j, k를 움직인다.
- nums[i] + nums[j] + nums[k] < 0 → j를 증가
- nums[i] + nums[j] + nums[k] > 0 → k를 감소
이렇게 j와 k를 좁히다가 nums[i] + nums[j] + nums[k] = 0인 인덱스를 발견하면 중복처리를 시작한다. 중복처리는 답을 찾은 순간 j와 k 중 아무 거나 하나를 잡고 중복이 제거될 때까지 좁히면 된다.
set을 사용해도 2 sum은 쉽게 구할 수 있다. 여기에 추가로 중복 제거를 하기 위해서 어떤 값이 정답으로 사용됐는지 따로 저장하는 set을 둬서 한번 더 검증한다.
코드
두 개의 포인터
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>> ans;
sort(nums.begin(), nums.end());
for(int i = 0; i < nums.size(); i++) {
if(i > 0 && nums[i] == nums[i-1]) continue;
int l = i+1, r = nums.size() - 1;
while(l < r) {
int sum = nums[i] + nums[l] + nums[r];
if(sum == 0) {
ans.push_back({ nums[i], nums[l], nums[r] });
while(l < nums.size() - 1 && nums[l] == nums[l+1]) l++;
l++;
}
else if(sum < 0) l++;
else r--;
}
}
return ans;
}
};
set으로 중복검사
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>> ans;
sort(nums.begin(), nums.end());
for(int i = 0; i < nums.size(); i++) {
if(i > 0 && nums[i] == nums[i-1]) continue;
unordered_set<int> check, s;
for(int j = i+1; j < nums.size(); j++) {
if(check.find(nums[j]) == check.end() && s.find(-nums[i]-nums[j]) != s.end()) {
ans.push_back({ nums[i], nums[j], -nums[i]-nums[j] });
check.insert(nums[j]);
check.insert(-nums[i]-nums[j]);
}
s.insert(nums[j]);
}
}
return ans;
}
};
'leetcode' 카테고리의 다른 글
leetcode 1326 - Minimum Number of Taps to Open to Water a Garden (0) | 2020.11.22 |
---|---|
leetcode 124 - Binary Tree Maximum Path Sum (0) | 2020.11.09 |
leetcode 1402 - Reducing Dishes (0) | 2020.10.15 |
leetcode 827 - Making A Large Island (0) | 2020.10.13 |
leetcode 85 - Maximal Rectangle (0) | 2020.10.13 |
댓글