# [Solution] Zero

:::info
:bulb: Unofficial solution written by sweetestlove.
:warning: Thuật toán đúng tuy nhiên code mẫu chưa test kĩ, có thể sai sót.
:::

## Bài 1: Bộ 3 số
:book: Thuật toán: Two Sum: One-pass Hash Table

Chúng ta cũng sẽ sắp xếp mảng và bỏ qua các phần trùng lặp.

Việc triển khai twoSum ở đây gần giống như trong Two Sum: One-pass Hash Table. Sự khác biệt duy nhất là kiểm tra để tránh trùng lặp. Vì mảng đã được sắp xếp, nên chúng ta chỉ có thể so sánh cặp tìm được với cặp cuối cùng trong kết quả.

Độ phức tạp: $O(n^2logn)$

:::spoiler C++ Solution

vector<vector<int>> fourSum(vector<int>& nums, int target) {
        vector<vector<int>> total;
        int n = nums.size();
        if(n<4)  return total;
        sort(nums.begin(),nums.end());
        for(int i=0;i<n-3;i++)
        {
            if(i>0&&nums[i]==nums[i-1]) continue;
            if(nums[i]+nums[i+1]+nums[i+2]+nums[i+3]>target) break;
            if(nums[i]+nums[n-3]+nums[n-2]+nums[n-1]<target) continue;
            for(int j=i+1;j<n-2;j++)
            {
                if(j>i+1&&nums[j]==nums[j-1]) continue;
                if(nums[i]+nums[j]+nums[j+1]+nums[j+2]>target) break;
                if(nums[i]+nums[j]+nums[n-2]+nums[n-1]<target) continue;
                int left=j+1,right=n-1;
                while(left<right){
                    int sum=nums[left]+nums[right]+nums[i]+nums[j];
                    if(sum<target) left++;
                    else if(sum>target) right--;
                    else{
                        total.push_back(vector<int>{nums[i],nums[j],nums[left],nums[right]});
                        do{left++;}while(nums[left]==nums[left-1]&&left<right);
                        do{right--;}while(nums[right]==nums[right+1]&&left<right);
                    }
                }
            }
        }
        return total;
    }

:::