[LeetCode] 18. 4Sum

문제 URL : https://leetcode.com/problems/4sum/

4Sum - LeetCode

 

문제 접근법 : 

 

배열 4개의 원소를 선택해서 합이 target이 되는것을 찾는 문제인데

 

4중for문을 이용하면 당연히 구해지겠지만

n^4 은 nums의 길이가 200까지라 8억이라 tle입니다.

정렬후 투포인터를 이용해 n^3을 만들수있습니다. 

 

소스코드 : 

 

class Solution {
public:
vector<vector<int>> fourSum(vector<int> &nums, int target)
{
    sort(nums.begin(), nums.end());
    set<vector<int>> s;
    int size = nums.size();
    for (int i = 0; i < size - 3; i++){
        for (int j =size-1; j >= i+3; j--){
            int l = i + 1;
            int r = j-1;
            long long sum = nums[i] + nums[j];
            while (l < r)
            {
                long long sum2 = sum + nums[l] + nums[r];
                if (sum2 <= target)
                {
                    if (sum2 == target)
                    {
                        s.insert({nums[i],nums[l],nums[r],nums[j]});
                    }
                    l++;
                }
                else
                {
                    r--;
                }
            }
        }
    }
    return vector<vector<int>> (s.begin(),s.end());
}
};

 

되게많이 틀렸습니다. 그이유는 투포인터를 이용안하고 풀어보고싶어서

시간복잡도 n^2으로 만들어봤지만 200개정도의 테스트케이스는 통과하는데 반례가 나오더군요

n^2(log(n)) 으로 할수없나 이분탐색 해봤는데도 잘 안되더군요

 

시간복잡도를 줄일수있는 해설이 있는 블로그가 있다면 알려주시면 감사하겠습니다.