Why my cpp solution time limited exceed? convert 4sum to 2 sum.


  • 0
    H

    vector<vector<int>> fourSum(vector<int>& nums, int target) {
    vector<vector<int>>res;
    if (nums.size()<4) return res;
    map<int, vector<pair<int, int>>>twoSum;

    for (int i = 0; i<nums.size(); ++i){
    	for (int j = i + 1; j<nums.size(); ++j){
    		twoSum[nums[i] + nums[j]].push_back({ i, j });
    	}
    }
    auto left = twoSum.begin();
    auto right = twoSum.end();
    right--;
    while (left != right){
    	if ((*left).first + (*right).first == target){
    		vector<pair<int, int>>vec1 = (*left).second;
    		vector<pair<int, int>>vec2 = (*right).second;
    		for (int i = 0; i<vec1.size(); ++i){
    			int pos1 = vec1[i].first;
    			int pos2 = vec1[i].second;
    			for (int j = 0; j<vec2.size(); ++j){
    				int pos3 = vec2[j].first;
    				int pos4 = vec2[j].second;
    				if (pos1 != pos3&&pos1 != pos4&&pos2 != pos3&&pos2 != pos4){
    					vector<int>temp{ nums[pos1], nums[pos2], nums[pos3], nums[pos4] };
    					res.push_back(temp);
    				}
    			}
    		}
    		++left; 
    	}
    	else if ((*left).first + (*right).first<target)  ++left;
    	else --right;
    }
    return res;
    

    }


Log in to reply
 

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