[leetcode] 18. 4Sum

문제

Given an array nums of n integers and an integer target, are there elements a, b, c, and d in nums such that a + b + c + d= target? Find all unique quadruplets in the array which gives the sum of target.

풀이

3Sum과 같은 방식으로 풀이한다.

Index 두 개를 잡고, 3Sum과 같은 방식으로 계산한다.

 

Time Complexity : $O(n^3)$

코드

class Solution {
public:
    vector< vector<int> > fourSum(vector<int> &nums, int target) {
        vector<vector<int> > ret;
        sort(nums.begin(), nums.end());
        int l = nums.size();
        for(int z=0;z<l-3;z++)
        {
            for (int i=z+1;i<l-2;i++)
            {
                int j=i+1, k=l-1;
                while(j<k)
                {
                    int sum = nums[z] + nums[i] + nums[j] + nums[k];
                    if (sum > target){k--; continue;}
                    if (sum < target){j++; continue;}

                    ret.push_back({nums[z],nums[i],nums[j],nums[k]});
                    while(j<l-1 && nums[j+1]==nums[j]) j++;
                    while(k>0 && nums[k-1]==nums[j]) k--;
                    j++, k--;
                }
                while(i<l-1 && nums[i+1]==nums[i]) i++;
            }
            
            while(z<l-1 && nums[z+1]==nums[z]) z++;
        }
        return ret;
    }
};