鏈接：

18. 四數(shù)之和

題意：

一個數(shù)組n，一個目標值t，在數(shù)組內(nèi)找四個數(shù)字和等于t，求能有多少種組合

解：

0716：一看怎么昨天卡沒打，原來昨天做的第一題不是每日一題，麻了

n很小，200，那么先排序，然后弄一個雙指針開雙循環(huán)l,r，確定每個組合的最大數(shù)字-數(shù)字4和最小數(shù)字-數(shù)字1，然后計算t-num1-num4，就可以得到該組合對應(yīng)的num2+num3 我們設(shè)為tL，然后再弄一個雙指針ll,rr在l,r內(nèi)找，這時，由于數(shù)組已經(jīng)排序了，所以如果nums[ll]+nums[rr]<tL就右移LL，如果nums[ll]+nums[rr]>tL就左移RR

當nums[ll]+nums[rr]==tL時，我們只需要將其和記錄結(jié)果的容器里最后一個比較是否相同就可以達到去重的效果（我直接用了暴力比較QWQ）

去重：

1、由于已經(jīng)排序，所以當新的L和上一個L相同時，跳過。相同數(shù)字第一個遇到的一定提供最大的范圍（即最小的L），比如 3,3,0,0,0,0…，取第一個3作為L，num2-4還可以選擇第二個3，和后面的所有數(shù)字；選取第二個3做為L，num2-4只能選擇后面的數(shù)字，所以選取第二個3做為L所推導(dǎo)的結(jié)果包含在取第一個3作為L的結(jié)果

2、現(xiàn)在已經(jīng)確定了該組合的第一個數(shù)字num1=nums[L]，這邊要開第二重循環(huán)去選取第四個數(shù)字num4=nums[R]，同樣，當新的R跟上一個R相同時，跳過，原因同 1

3、確定了num1和num4，再找num2和num3就很簡單了，上面也提過了，不用雙循環(huán)，頂多遍歷一遍 l,r

4、由于num1逐漸增大且不重復(fù)，在同一個num1下num4逐漸減小且不重復(fù)，所以答案容器里末尾要么是不同的num1開頭，要么是相同的num1開頭不同的num4結(jié)尾，要么是相同的num1num4，前面兩種情況和現(xiàn)在明顯不相同，在第三種情況下，由于LL和RR的起始值固定，且移動方向固定（向數(shù)組中間），且數(shù)組有序，所以如果不和容器末尾相同，則在容器中一定不存在與之相同的答案

5、由此可知，容器中答案排序是：num1從小到大，num1相同時num4從大到小，num1和num4均相同時num2num3從兩邊到中間

實際代碼：

#include<bits/stdc++.h>
using namespace std;
bool comp(const vector<int>& A,const vector<int>& B)
{
    for(int i=0;i<4;i++)
    {
        if(A[i]!=B[i])return true;
    }
    return false;
}
vector<vector<int>> fourSum(vector<int>& nums, int target)
{
    sort(nums.begin(),nums.end());//先排序 
    //for(auto i:nums) cout<<i<<" ";
    //cout<<endl;
    vector<vector<int>>ans;int lg=nums.size();
    for(int l=0,r=lg-1;l<r;l++)
    {
        if(l && nums[l-1]==nums[l] )continue;//確定數(shù)字1 不重復(fù) 
        for(;l<r;r--)
        {
            if(r<lg-1 && nums[r+1]==nums[r]) continue;//確定數(shù)字4 在當前數(shù)字1不重復(fù) 
            //cout<<l<<"-N1-"<<r<<endl;
            long long targetL=(long long)target-nums[l]-nums[r];//新的目標 
            for(int ll=l+1,rr=r-1;ll<rr;)
            {
                //cout<<ll<<"-N2-"<<rr<<endl;
                long long now=(long long)nums[ll]+nums[rr];//當前值 
                if(now==targetL)
                {
                    vector<int>temp{nums[l],nums[ll],nums[rr],nums[r]};
                    //去重 
                    if(!ans.empty() && comp( temp,*(ans.rbegin()) )) ans.push_back(temp);
                    if(ans.empty()) ans.push_back(temp);
                    ll++;rr--;
                }
                else if(now<targetL) ll++;
                else rr--;
            }
        }
        r=lg-1;//重置右指針 
    }
    return ans;
}
int main()
{
    vector<int> nums;int target;
    cin>>target;int temp;
    while(cin>>temp)
    {
        nums.push_back(temp);
    }
    vector<vector<int>>ans=fourSum(nums,target);
    for(auto &i:ans)
    {
        for(auto j:i)
        {
            cout<<j<<" ";
        }
        cout<<endl;
    }
    return 0;
}

限制：文章來源地址http://www.zghlxwxcb.cn/news/detail-566853.html

• 1 <= nums.length <= 200
• -109 <= nums[i] <= 109
• -109 <= target <= 109

到了這里，關(guān)于2023-07-15力扣每日一題的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！