題目來(lái)源：https://leetcode.cn/problems/4sum/description/

成都創(chuàng)新互聯(lián)公司是一家專注于網(wǎng)站制作、成都網(wǎng)站設(shè)計(jì)與策劃設(shè)計(jì),遠(yuǎn)安網(wǎng)站建設(shè)哪家好?成都創(chuàng)新互聯(lián)公司做網(wǎng)站,專注于網(wǎng)站建設(shè)十載,網(wǎng)設(shè)計(jì)領(lǐng)域的專業(yè)建站公司;建站業(yè)務(wù)涵蓋:遠(yuǎn)安等地區(qū)。遠(yuǎn)安做網(wǎng)站價(jià)格咨詢:18980820575

C++題解：第一次嘗試，數(shù)組排序后，分別從兩端各自往里走，單個(gè)樣例都能通過(guò)，但是超時(shí)

class Solution {
public:
    vector>fourSum(vector& nums, int target) {
        sort(nums.begin(),nums.end());
        int len = nums.size();
        int iii,jjj;
        vector>daan;
        for(int ii = 0; ii< len-3; ii++){
            if(nums[ii] >250000000) break;
            for(int jj = len-1; jj >ii+2; jj--){
                if(nums[jj]< -250000000) break;
                for(int kk = ii+1; kk< jj-1; kk++){
                    if(nums[ii] + nums[jj] + nums[kk] >1000000000) break;
                    for(int ll = jj-1; ll >kk; ll--){
                        if(nums[ii] + nums[jj] + nums[kk] + nums[ll] == target) {
                            daan.push_back({nums[ii], nums[kk], nums[ll], nums[jj]});
                            //cout<ii+2)) jj--;
            }
            while((nums[ii+1] == nums[ii])&&(ii+1< len-3)) ii++;
        }
        return daan;
    }
};

第一次遇到測(cè)試用例全部通過(guò)但是超時(shí)的情況

將第四個(gè)數(shù)的位置定位成二分查找。對(duì)一些超出int的范圍的情況做一些限制

class Solution {
public:
    vector>fourSum(vector& nums, int target) {
        sort(nums.begin(),nums.end());
        int len = nums.size();
        int jjj,kkk,ll;
        vector>daan;
        for(int ii = 0; ii< len-3; ii++){
            if(nums[ii] >250000000) break;
            for(int jj = len-1; jj >ii+2; jj--){
                if(nums[jj]< -250000000) break;
                for(int kk = ii+1; kk< jj-1; kk++){
                    if(nums[ii] + nums[jj] + nums[kk] >1000000000) break;
                    kkk = kk; jjj = jj;
                    ll = floor((kkk+jjj)/2);
                    while(ll!=kkk){
                        if((nums[kk]/2 + nums[ll]/2 + nums[jj]/2< -500000000)or(nums[ii] + nums[jj] + nums[kk] + nums[ll] >target)){
                            jjj = ll;
                            ll = floor((kkk+jjj)/2);
                        }
                        else if((nums[kk]/2 + nums[ll]/2 + nums[jj]/2 >500000000)or(nums[ii] + nums[jj] + nums[kk] + nums[ll]< target)){
                            kkk = ll;
                            ll = floor((kkk+jjj)/2);
                        }
                        else{   //相等的情況
                            daan.push_back({nums[ii], nums[kk], nums[ll], nums[jj]});
                            break;
                        }
                    }
                    while((nums[kk+1] == nums[kk])&&(kk+1< jj-1)) kk++;
                }
                while((nums[jj] == nums[jj-1])&&(jj-1 >ii+2)) jj--;
            }
            while((nums[ii+1] == nums[ii])&&(ii+1< len-3)) ii++;
        }
        return daan;
    }
};

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級(jí)流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級(jí)服務(wù)器適合批量采購(gòu)，新人活動(dòng)首月15元起，快前往官網(wǎng)查看詳情吧

分享標(biāo)題：力扣18.四數(shù)之和-創(chuàng)新互聯(lián)
本文URL：http://weahome.cn/article/dhjdjp.html