[LeetCode] 18. 4Sum

https://leetcode.com/problems/4sum/

4Sum - LeetCode

4Sum

 

역시나 3Sum의 업그레이 버전이다.

풀이는 3Sum에서 한개의 수를 고정하고 투 포인터를 이용했다면, 이 문제에서는 두 개를 고정하고 투 포인터를 이용해주면 된다.

더할때 integer 범위를 초과할 수 있으니 주의하자.

 

전체 풀이 코드

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