https://leetcode.com/problems/3sum/description
Q. 숫자배열 nums가 주어질 때, 세 수가 다르면서 그 합이 0 이 되는 수들의 집합을 구하라.
이때 결과값이 중복되어서는 안된다.
Solution.
숫자 두개의 합에 대해서 구할때는 hash 를 쓰면된다.
하지만, 셋은 조금 접근법이 다르다.
두개에 대해서는 하나를 찾으면 나머지를 바로 알 수 있지만,
세개는 남은 두개를 다시 찾기 쉬운 형태로 만들어 놓아야 한다.
여기서는 nums를 정렬시켜 놓아 이 형태로 만든다.
즉, 첫 수는 loop로 정하고, 나머지 두 수는 남은 수 중 가장 큰 수와 작은 수를 비교 한다.
이때 두 수의 합이 첫 수보다 크다면, 큰수 쪽을 작은 쪽으로 이동 시킨다.
작다면, 작은 수 쪽은 큰쪽으로 이동 시킨다.
우선 큰 틀은 아래와 같다.
다만, 중복되는 수가 있으면 안된다고 하였으므로, 여러 가지 방법으로 한 수 셋만 취하면 되겠다.
코드
더보기
public IList<IList<int>> ThreeSum(int[] nums)
{
Array.Sort(nums);
HashSet<string> setFreq = new HashSet<string>();
IList<IList<int>> listRet = new List<IList<int>>();
for(int q = 0; q < nums.Length-2; ++q)
{
int top = nums[q];
int left = q+1;
int right = nums.Length-1;
while(left<right)
{
int sum = top + nums[left] + nums[right];
if(sum == 0)
{
string key = $"{nums[q]},{nums[left]},{nums[right]}";
if(!setFreq.Contains(key))
{
listRet.Add( new List<int>(){ nums[q], nums[left], nums[right]} );
setFreq.Add(key);
}
++left; --right;
}
else if(sum > 0)
--right;
else
++left;
}
}
return listRet;
}
Outcome.
보통 중복수를 제거해 나가는 과정이 최적화가 잘 되어 있을 시 더 나을 결과를 얻는 듯 하다.
'Leetcode > Challenges' 카테고리의 다른 글
[Misc][Medium] 31. Next Permutation (1) | 2024.04.26 |
---|---|
[Two Pointers][Hard] 42. Trapping Rain Water (0) | 2024.04.25 |
[Stack][Medium] 155. Min Stack (0) | 2024.04.23 |
[Sliding Window][Hard] 239. Sliding Window Maximum (1) | 2024.04.19 |
[Matrix][Medium] 240. Search a 2D Matrix II (0) | 2024.04.17 |