C++ O(N^2) solution, only 8ms.


  • 0
    M
    class Solution {
    public:
        int threeSumClosest(vector<int>& nums, int target) {
            sort(nums.begin(), nums.end());
    
            int n = nums.size();
            int closest_sum = nums[n-3] + nums[n-2] + nums[n-1];
    
            if (closest_sum <= target) {
                return closest_sum;
            }
    
            int min_diff = closest_sum - target;
    
            for (int i = 0, j, k; i < n-3; i++) {
                if (i > 0 && nums[i] == nums[i-1]) {
                    continue;
                }
    
                int minsum = nums[i] + nums[i+1] + nums[i+2];
                int diff1 = minsum - target;
                if (diff1 >= 0) {
                    if (diff1 < min_diff) {
                        closest_sum = minsum;
                    }
                    break;
                }
    
                int maxsum = nums[i] + nums[n-2] + nums[n-1];
                int diff2 = target - maxsum;
                if (diff2 >= 0) {
                    if (diff2 < min_diff) {
                        closest_sum = maxsum;
                        min_diff = diff2;
                    }
                    continue;
                }
    
                j = i + 1, k = n - 1;
                while (j < k) {
                    if (nums[j] == nums[j-1]) {
                        j++;
                    } else if (nums[k] == nums[k+1]) {
                        k--;
                    } else {
                        int sum = nums[i] + nums[j] + nums[k];
                        int diff = sum - target;
                        if (diff < 0) {
                            j++;
                            diff = -diff;
                        } else if (diff > 0) {
                            k--;
                        } else {
                            return sum;
                        }
                        if (diff < min_diff) {
                            min_diff = diff;
                            closest_sum = sum;
                        }
                    }
                }
            }
            return closest_sum;
        }
    };

  • 0
    Y

    can you tell us what is the critical idea in your code to reduce the run time from 16ms to 8ms?


  • 0
    Q

    This is a wrong answer when you try this as input, although it is accepted.

    [1,1,1,4,7,9]
    6

Log in to reply
 

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