---
# System prepended metadata

title: '[Solution] Zero'

---

# [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
```c++
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;
    }

```
:::


