[leetcode]15. 3Sum

문제
배열안의 요소 중 모두 더했을때 0이되는 3개 요소의 조합을 구하기.
중복되는 조합이면 안된다. 이 때 중복은 index의 중복을 말하는 듯.

https://leetcode.com/problems/3sum/submissions/1677996513/

정수 배열 nums, 모든 세개 숫자의 조합. 인덱스가 서로 달라야한다. (중복으로 들어가면 안된다)
그리고 중복된 숫자도 들어가면 안된다. 즉 순열이 아닌 조합이다.

양 끝에 포인터를 하나씩 놓고 두 포인터 가리키는 정수의 합이, 찾으려는 합보다 작으면 왼쪽 포인터를 우축으로 한칸 옮기고, 크면 오른쪽 포인터를 좌측으로 한 칸 옮기면서 결국 찾으려는 값으로 두개의 포인터를 수렴시킨다.
그럼 정렬이 필요하다.

`//2. 투포인터로 풀기

/*
우선 내가 문제에 대한 이해가 틀렸다. 숫자의 순서가 다르다고 하더라도, 같은 숫자의 조합을 가지고 있다면 안된다. 
값이 원하는 값보다 작으면 오른쪽 값을 옮기고, 크면 왼쪽 값을 옮기는 투포인터 전략을 취해보았다. 

 */

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var threeSum = function(nums) {
  const triplets = []
  nums.sort((a,b)=>a-b)
  for(let i =0;i<nums.length -2 ;i++){
    if (i > 0 && nums[i] === nums[i - 1]) continue;
  	let low = i+1
   	,high = nums.length -1
    
    while(low < high){
     	const three_sum = nums[i] + nums[low] + nums[high]
        if(three_sum<0){
        	low +=1
        }
      	else if(three_sum >0){
        	high -=1
        }
		else{
        	triplets.push([nums[i],nums[low],nums[high]])
            while (low < high && nums[low] === nums[low + 1]) low++;
            while (low < high && nums[high] === nums[high - 1]) high--;
          	low = low+1
            high = high -1                 
        }
    }
  }
  return triplets
};