Approach

• nums 벡터의 요소들을 sort함수를 통해 정렬해주었다.
• 정렬해준 첫 번째 요소의 값이 0보다 크다면 이후의 값들은 다 양수이기 때문에 3개의 합이 0이 나올수가 없어서 빈 ans벡터를 return해준다.
• 본격적으로 for문을 통해 nums의 요소들을 비교해준다.
  • 만약 nums[i]의 값이 0보다 크다면 위와 동일하기때문에 break문으로 for문을 탈출한다.
  • 양수가 아니라면 투 포인터를 활용하여 nums[i]값과 다른 두 nums값을 합하여 0인지 아닌지 찾는다.
    • 하나의 포인터는 i의 다음 인덱스인 i+1을 가리키고, 나머지 포인터는 nums의 맨 마지막 요소 인덱스를 가리킨다.
  • left(i+1부터 시작) 포인터가 right(맨 끝에서 부터 시작) 포인터보다 커질때 까지 while문을 실행한다.
    • sum변수에 nums[i], nums[left], nums[right]를 더해 값을 비교한다.
    • sum의 값이 음수면 left 인덱스에 +1을 더해준다.
    • sum의 값이 양수면 right 인덱스에 -1을 더해준다.
    • sum의 값이 0이면 ans에 세 nums를 배열형식으로 넣어준다.
    • nums[i]와 또 다른 두 수의 조합이 0을 만들 수 있기때문에 right값을 1 감소시켜주는데 감소시킨 nums[right]값이 이전의 nums[right+1]값과 같다면 중복된 결과를 다시 넣어주기 때문에 조건문에 해당 조건을 걸어주었다.
• ans 벡터를 정렬 시키고 중복된 값을 erase와 unique를 활용하여 지워주었다.

Code

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> ans;

        sort(nums.begin(), nums.end());

        if(nums[0] > 0) return ans;

        for(int i = 0; i < nums.size(); i++)
        {
            if(nums[i] > 0) break;

            int left = i+1, right = nums.size()-1;

            while(left < right)
            {
                int sum = nums[i] + nums[left] + nums[right];

                if(sum < 0) left++;
                else if(sum > 0) right--;
                else 
                {
                    ans.push_back({nums[i], nums[left], nums[right--]});

                    while((left < right) && (nums[right] == nums[right+1]))
                    {
                        right--;
                    }
                }
            }
        }

        sort(ans.begin(), ans.end());
        ans.erase(unique(ans.begin(), ans.end()), ans.end());

        return ans;
    }
};

Result

---

추가적인 해결방법

• 이전의 요소와 같은 값인지 비교해주는 것을 앞당겨왔다.
• 정렬한 요소의 값에서 nums[i]의 값이 이전에 비교한 nums[i-1]값과 같다면 continue로 무시하고 이어서 진행하게한다.

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> ans;

        sort(nums.begin(), nums.end());

        if(nums[0] > 0) return ans;

        for(int i = 0; i < nums.size()-1; i++)
        {
            if(nums[i] > 0) break;
            if((i > 0) && (nums[i] == nums[i-1])) continue;

            int left = i+1, right = nums.size()-1;

            while(left < right)
            {
                int sum = nums[i] + nums[left] + nums[right];

                if(sum < 0) left++;
                else if(sum > 0) right--;
                else 
                {
                    ans.push_back({nums[i], nums[left], nums[right--]});

                    while((left < right) && (nums[right] == nums[right+1]))
                    {
                        right--;
                    }
                }
            }
        }

        return ans;
    }
};