My 13ms C++ solution


  • 0
    X

    My first time submitting a code on here. Let me know what you think or if you have questions!

    class Solution {
    public:
    	std::vector<std::vector<int>> static FourSum(std::vector<int>& nums, int target) {
    		std::vector<std::vector<int>> solution;
    		if (nums.size() < 4) { return solution; }
    		std::sort(nums.begin(), nums.end());
    		int biggestIndexDToCheck = nums.size() - 1;
    		for (int indexA = 0; indexA < nums.size() - 3; ++indexA) {
    			if (nums[indexA] + nums[indexA + 1] + nums[indexA + 2] + nums[indexA +3] > target) { break; }
    			if (indexA > 0 && nums[indexA - 1] == nums[indexA]) { continue; }
    			for (int indexD = biggestIndexDToCheck; indexD > 2; --indexD) {
    				if (nums[biggestIndexDToCheck] + nums[biggestIndexDToCheck - 1] + nums[biggestIndexDToCheck - 2] + nums[biggestIndexDToCheck - 3] < target) { return solution; }
    				if (indexD < nums.size() - 1 && nums[indexD] == nums[indexD + 1]) { continue; }
    				int greatestSum = nums[indexA] + nums[indexD - 2] + nums[indexD - 1] + nums[indexD];
    				if (greatestSum < target) {
    					break;
    				}
    				int leastSum = nums[indexA] + nums[indexA + 1] + nums[indexA + 2] + nums[indexD];
    				if (leastSum > target) {
    					biggestIndexDToCheck = indexD - 1;
    					continue;
    				}
    				int indexB = indexA + 1, indexC = indexD - 1;
    				while (indexB < indexC) {
    					int sum = nums[indexA] + nums[indexB] + nums[indexC] + nums[indexD];
    					if (sum > target) {
    						do { --indexC; } while (nums[indexC] == nums[indexC + 1]);
    					} else if (sum < target) {
    						do { ++indexB; } while (nums[indexB] == nums[indexB - 1]);
    					} else {
    						std::vector<int> combo = { nums[indexA], nums[indexB], nums[indexC], nums[indexD] };
    						solution.push_back(combo);
    						do { ++indexB; } while (nums[indexB] == nums[indexB - 1]);
    						do { --indexC; } while (nums[indexC] == nums[indexC + 1]);
    					}
    				}
    			}
    		}
    		return solution;
    	}
    };

Log in to reply
 

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