[알고리즘] 7번째 알고리즘 문제

[SongGwanSeok]

📝 Description

무엇을?

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

왜?

• (ex 사용자를 인증하기 위해)

❗️Todo

• [ ]
• [ ]
• [ ]

ETC

기타사항

[SongGwanSeok]

3Sum

class Solution {
public:    
    vector<vector<int>> threeSum(vector<int>& nums) {
        set<vector<int>> zero_sum_set;
        sort(nums.begin(), nums.end());
        int lastNum = nums[0] - 1;

        for(int i = 0; i < nums.size()-2; i++){
            int findNum = -nums[i];

            if (nums[i] == lastNum)
                continue;

            int l = i+1;
            int r = nums.size()-1;

            while(l < r) {
                int sum = nums[l] + nums[r];
                if (sum > findNum) {
                    r--;
                } else if (sum < findNum) {
                    l++;
                } else {
                    vector<int> zeroIdxList = {nums[i], nums[l], nums[r]};
                    zero_sum_set.insert(zeroIdxList);
                    while(l < r && nums[l] == nums[l+1]){
                        l++;
                    }
                    while(l < r && nums[r] == nums[r-1]){
                        r--;
                    }
                    l++;
                    r--;
                }
            }
        }

        vector<vector<int>> zero_sum_list(zero_sum_set.begin(), zero_sum_set.end());

        return zero_sum_list;
    }
};

[SongGwanSeok]

4sum

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        long lTarget = target;
        vector<vector<int>> res;
        set<vector<int>> res_set;

        if(nums.size() < 4) return res;

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

        for(int i = 0; i < nums.size()-3; i++){
            long long num1 = nums[i];

            for(int j = i + 1; j < nums.size()-2; j++){
                long long num2 = nums[j];
                int l = j + 1;
                int r = nums.size() - 1;

                while(l < r){
                    long long assertTarget = num1 + num2 + nums[l] + nums[r];
                    if(assertTarget < target){
                        l++;
                    }

                    else if(assertTarget > lTarget){
                        r--;
                    }
                    else if(assertTarget == lTarget){
                        vector<int> targetSumList = {nums[i], nums[j], nums[l], nums[r]};

                        res_set.insert(targetSumList);
                        l++;
                        r--;

                        while(l < r && nums[l-1] == nums[l]){
                            l++;
                        }
                        while(l < r && nums[r+1] == nums[r]){
                            r--;
                        }
                    }
                }

            }
        }
        for(vector<int> rs: res_set){
            res.push_back(rs);
        }
        return res;
    }
};