力扣18.四数之和-创新互联

题目来源：https://leetcode.cn/problems/4sum/description/

C++题解：第一次尝试，数组排序后，分别从两端各自往里走，单个样例都能通过，但是超时

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;
    }
};

第一次遇到测试用例全部通过但是超时的情况

将第四个数的位置定位成二分查找。对一些超出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;
    }
};

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧