15. 3Sum
15. 3Sum
문제
Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.
Notice that the solution set must not contain duplicate triplets.
Example 1:
Input: nums = [-1,0,1,2,-1,-4] Output: [[-1,-1,2],[-1,0,1]] Explanation: nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0. nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0. nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0. The distinct triplets are [-1,0,1] and [-1,-1,2]. Notice that the order of the output and the order of the triplets does not matter.
Example 2:
Input: nums = [0,1,1] Output: [] Explanation: The only possible triplet does not sum up to 0.
Example 3:
Input: nums = [0,0,0] Output: [[0,0,0]] Explanation: The only possible triplet sums up to 0.
Constraints:
3 <= nums.length <= 3000 -10^5 <= nums[i] <= 10^5
문제 해석
- 벡터 nums 에서 3개의 합이 0 인 숫자들의 집합 vector를 찾는 문제
- 각 vector 는 고유(unique) 해야한다.
구현
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
sort(nums.begin(), nums.end());
vector<vector<int>> ans;
// 기본 설정
if(nums.size() < 3) // 문제가 3개 항의 합이 0인 것을 찾는 것이다.
{
return {};
}
if(nums[0] > 0) //오름차순으로 정리했기 때문에 첫항이 0보다 크면 절대 3개의 항 합이 0이 될 수가 없다.
{
return {};
}
for(int i = 0; i < nums.size(); i++)
{
int left = i + 1;
int right = nums.size() - 1;
int sum = 0;
// nums[i] 가 3개의 항 중 가장 작은 수인데 이것이 0보다 커지면 3개 합 0을 만들 수가 없다.
if(nums[i] > 0)
{
break;
}
// 중복없는 결과를 도출해야 하기 때문에 똑같은 값은 넘어간다.
if(i > 0 && nums[i] == nums[i-1])
{
continue;
}
while(left < right)
{
sum = nums[i] + nums[left] + nums[right];
if(sum > 0)
{
right--;
}
else if(sum < 0)
{
left++;
}
else // sum = 0
{
ans.push_back({nums[i], nums[left], nums[right]});
int last_left = nums[left];
int last_right = nums[right];
while(left < right && nums[left] == last_left)
{
left++;
}
while(left < right && nums[right] == last_right)
{
right--;
}
}
}
}
return ans;
}
};
코드 해석
- 간단한 해석은 주석으로 달아놨기 때문에 이해하기 어려웠던 부분만 정리한다.
else // sum = 0
{
ans.push_back({nums[i], nums[left], nums[right]});
int last_left = nums[left];
int last_right = nums[right];
while(left < right && nums[left] == last_left)
{
left++;
}
while(left < right && nums[right] == last_right)
{
right--;
}
}
- 이 문제에서 가장 중요한 부분이라고 생각
- 각 3개 항의 고유성을 만들어 주는 코드이다.
- 3개의 항의 합이 0 이라면 vector ans 에 넣는다.
- 그 넣은 값들을 ‘last_left 와 last_right 에 저장해둔다.
- 만약 이 두개가 같다면 이미 ans 벡터에 넣은 중복된 값이기에 while 문에 걸린다면 left 와 right 를 증감해줘야하는 것이다.
시간, 공간복잡도
- 시간 복잡도는 sort 정렬로 인하여 O(nlogn)이다.
- 공간 복잡도는 결과 배열 O(n) 정렬 때 사용한 공간 O(logn) 으로 결국 O(n)이 된다.