Share my easy understanding code beating 92% in C++


  • 3
    S
       vector<vector<int>> result;
    vector<int>  temp;
    int L =nums.size();
        sort(nums.begin(),nums.end());//排序
    //第一层循环,加上预判
    for (int i=0;i<L-3&&nums[i]+nums[i+1]+nums[i+2]+nums[i+3]<=target;i++){  //第一层循环
    	if (i!=0&&nums[i]==nums[i-1])  continue;//跳过重复元素
        if(nums[i]+nums[L-1]+nums[L-2]+nums[L-3]<target) continue;//预判
    	int target3 = target -nums[i];//后三个变量之和等于target3
    	//第二层for循环,加上预判
    	for(int j=i+1;j<L-2&&nums[j]+nums[j+1]+nums[j+2]<=target3;j++){
    		
    		if (j!=i+1&&nums[j]==nums[j-1])  continue;//跳过重复元素
    		if (nums[j]+nums[L-1]+nums[L-2]<target3) continue;//预判
    		int target2 = target3 -nums[j];//最后两个变量之和等于target2
    		//第三层for循环
    		for(int m=j+1,n=L-1;;){
    			while(m!=j+1&&nums[m]==nums[m-1]) m++;//跳过重复元素
    			while(n!=L-1&&nums[n]==nums[n+1]) n--;//跳过重复元素
    			if (m>=n) break;
    
    			if(nums[m]+nums[n]>target2) n--;
    			else if (nums[m]+nums[n]<target2) m++;
    			else {
    			temp.push_back(nums[i]);
    			temp.push_back(nums[j]);
    			temp.push_back(nums[m]);
    			temp.push_back(nums[n]);
    			result.push_back(temp);
    			temp.clear();
    			n--;m++;
    			}					
    		}	
    	}
    }
       return result;
    

  • 1
    Y

    what's the time complexity of your code???


  • 0
    S

    it‘s hard to know,because the for sentence can skip many invalid cases.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.