My C++ solution using binary search. O(nlgn)~O(n^2*lgn)


  • 0
    L

    I add binary search to replace the j++ / k--
    And the time cost reduced from 9ms to 6ms, according to the inaccurate evaluation of leetcode

    In best situation , time cost can be O(nlgn)

    For example,
    [1,2,...,100]
    1000

    However, in worst situation, time cost maybe reach O(n^2*lgn)
    Though I can't find exactly such a case, this case may be close:
    [0,1,3,5,...49,51,52,54,...100]
    102

    when i==0, the while loop of j and k costs nlgn

    All in all, I think the binary search does more good than harm.

        // find the last element equal to or smaller than the key, in the range left to right
        inline int findLastEqualSmaller(const vector<int> &array, int key, int left, int right) {
            // must use <=
            while (left <= right) {
                int mid = (left + right) / 2;
                if (array[mid] > key) {
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            }
            return right;
        }
    
        // find the first element equal or larger than the key, int the range left to right
        inline int findFirstEqualLarger(const vector<int> &array, int key, int left, int right) {
            // must use <=
            while (left <= right) {
                int mid = (left + right) / 2;
                if (array[mid] >= key) {
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            }
            return left;
        }
    
        int threeSumClosest(vector<int> &nums, int target) {
            int min = INT_MAX, ans = 0, temp;
            sort(nums.begin(), nums.end());
            for (int i = 0; i < nums.size() - 2; i++) {
                int j = i + 1, k = nums.size() - 1, sum = target - nums[i];
                while (j < k) {
                    temp = sum - nums[j] - nums[k];
                    if (abs(temp) < min) {
                        min = abs(temp);
                        ans = target - temp;
                        if (min == 0) return ans;
                    }
                    if (nums[j] + nums[k] < sum) {
                        temp = findLastEqualSmaller(nums, sum - nums[k], j + 1, k - 1);
                        j == temp ? j++ : j = temp;
                    } else {
                        temp = findFirstEqualLarger(nums, sum - nums[j], j + 1, k - 1);
                        k == temp ? k-- : k = temp;
                    }
                }
            }
            return ans;
        }
    

Log in to reply
 

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