O(n^2) solution


  • 0
    D
    class Solution {
    public:
    
        int threeSumClosest(vector<int> &num, int target) {
            int n = num.size();
            sort(num.begin(), num.end());
            int min_difference = INT_MAX, sum = 0;
            for(int i = 0; i < n-2; i++) {
                int j = i + 1, k = n-1;
                while (j < k) {
                    int difference = target - num[i] - num[j] - num[k];
                    if (abs(difference) < min_difference) {
                        min_difference = abs(difference);
                        sum = num[i] + num[j] + num[k];
                    }
                    if (difference > 0) {
                        j++;
                    } else {
                        k--;
                    }
                }
            }
            return sum;
        }
    };

Log in to reply
 

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