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.
숫재 배열이 있는데 3개의 각각 다른 숫자를 더해서 0이되는 경우를 찾아서 반환하하는 문제이다
중복이 없어야 한다
예를 들어
[-4, -1, -1, 0, 1, 2] 에서 3개 더해서 0 되는 경우는
[-1, -1, 2], [-1, 0, 1], [-1, 0, 1] 인데 2번째 3번째가 중복되므로 하나 제거해서
[-1, -1, 2], [-1, 0, 1] 을 반환해야 한다는것이다..
이 문제를 풀기 위해서 먼저 nums 배열을 정렬해줬다. 그리고 3개 더하는 경우의 수를 계산하는 것보다 2개 더해서 0으로 만드는 경우의 수 부터 생각해보기로 하였다
2개를 더해서 0으로 만드는 방법부터 생각해보니 쉽게 더하는 알고리즘을 생각해낼 수 있었다. 배열의 양쪽 끝에서부터 더해서 2개 더해서 0 나오는 경우를 생각해보면 된다.
L, R 인덱스 변수가 있다고 해보자. L=배열의 첫번째, R=배열의 마지막, 으로 한다. 아니면 정중앙에서 부터 시작해도 될듯하긴하다(L=2,R=3 이런식으로 이 경우 로직이 많이 바뀐다) 어쨋든 둘다 더한 값에 따라서 L 과 R을 움직여가면서 더하면 된다.
nums[L]+nums[R] > 0 이면 R--
nums[L]+nums[R] < 0 이면 L++
nums[L]+nums[R] ==0 이면 nums[L], nums[R] 값 저장
L >= R 이면 종료
이렇게 하면 nums[L]+nums[R]==0 이되는 경우를 효율적으로 찾을 수 있을거 같다
이방식을 3개를 더하는 알고리즘에도 응용해보았다
L,M,R 인덱스3개 정의하자
L 하나는 고정하고 M,R 2개 만 움직여 가면서 더한다
이중 FOR문 이면 될거 같다
의사코드(Pseudo code)
L=0
{
M=L+1, R=nums.length-1
while(M<R) //M>=R 이면 종료
{
nums[L] + nums[M] + nums[R] >0 면 R--
nums[L] + nums[M] + nums[R] <0 면 M++
nums[L] + nums[M] + nums[R] == 0 면 해시셋에 저장 및 M++ (아니면 R--해도될거같긴하다)
}
nums[L] > 0 이면 break;
L++ 하고 위의 과정반복
}
그리고 중복제거를 위해 해시셋을 사용했는데 아무래도 더 좋은 방법이 당장 떠오르지 않아서 사용하였다
public List<List<Integer>> threeSum(int[] nums)
{
List<List<Integer>> ret = new ArrayList<List<Integer>>();
Arrays.sort(nums);
HashSet<List<Integer>> hashSet = new HashSet<>();
for(int l = 0; l < nums.length; ++l)
{
int m = l+1;
int r = nums.length-1;
while(m < r)
{
int temp = nums[l]+nums[m]+nums[r];
if(temp >0)
r--;
else if(temp < 0)
m++;
else
{
List<Integer> list = Arrays.asList(nums[l], nums[m], nums[r]);
hashSet.add(list);
m++;
}
}
if(nums[l] > 0)
break;
}
for(List<Integer> element : hashSet)
{
ret.add(element);
}
return ret;
}
다른 사람의 풀이를 참조한 결과 중복저장이 되지 않도록 하는 방법을 찾았다
L M R
[-4, -1, -1, 0, 1, 2]
위에서 M인덱스 탐색시에 M 과 M+1 이 같을경우
M++을 하는 방식으로 해결하고 있다 나중에 다시 풀어봐야겠다