[Two Pointers][Medium] 15. 3Sum

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.

 

보통 중복수를 제거해 나가는 과정이 최적화가 잘 되어 있을 시 더 나을 결과를 얻는 듯 하다.