[TwoPointers][Medium] 15. 3Sum

https://leetcode.com/problems/3sum/description/ 

 

정수 배열이 주어질 때, 세 수의 합이 0 이 되는 수를 찾아라.

 

우선 정렬이 필요하다. 

다음으로 첫수를 정하고, 

그 뒤로는 두 수의 합을 구하는 로직과 같다. 

 

다만, 중복이 없어야 하므로, 이는 여러 방법을 사용할 수 있겠다. 

 

코드 

 

vector<vector<int>> threeSum(vector<int>& nums) 
{
    sort(nums.begin(), nums.end());

    vector<vector<int>> vRet;
    set<string> vBuff;
    for (int q = 0; q < nums.size() - 2; ++q)
    {
        int num0 = nums[q];
        int left = q + 1;
        int right = nums.size() - 1;
        int target = -num0;
        while (left < right)
        {
            int sum = nums[left] + nums[right];
            if (sum == target)
            {
                string temp = to_string(num0) + "_" + to_string(nums[left]) + "_" + to_string(nums[right]);
                if (vBuff.find(temp) == vBuff.end())
                {
                    vRet.push_back(vector<int>{ num0, nums[left], nums[right] });
                    vBuff.insert(temp);
                }
                ++left; --right;
            }
            else if (sum < target)
                ++left;
            else if (sum > target)
                --right;
        }
    }
    return vRet;
}

 

결과