Best 3Sum Closest Solutions


  • 0
    J

    This problem is similar to other 3 sum problem in leetcode, and here we would describe several solutions to it.

    Approach #1 Brute Force [Time Limit Exceeded]

    Intuition
    The simplest way to solve the problem is iterate all possibilities and check compare them, and you can get the answer.

    Algorithm
    Suppose we have i, j, k, which a = nums[i], b = nums[j], c = nums[k]. And i,j,k satisfy 0 <= i < j < k < n; If we use 3 for loop, we could iterate all conditions, and get the answer.

    c++ code

    class Solution {
    public:
        int threeSumClosest(vector<int>& nums, int target) {
            if (nums.size() < 3) return 0;
            int n = nums.size();
            int res = nums[n-1] + nums[n-2] + nums[n-3];
            int t;
            for (int i = 0; i < n; i++) {
                for (int j = i+1; j < n; j++) {
                    for (int k = j+1; k < n; k++) {
                        t = nums[i] + nums[j] + nums[k];
                        if (abs(res-target) > abs(t-target)) {
                            res = t;
                        }
                    }
                }
            }
            return res;
        }
    };
    

    Complexity Analysis
    The complexity is O(n^3). Cause we use 3 for loop here, and each complexity is O(n). The this approach will exceed the time limit.

    Approach #2 Two Pointers Method [Accepted]

    Algorithm
    Here we use 3 pointer to solve this problem.

    1. Suppose we have a sorted array, if the array is no already sorted, we can use sort function to make it sorted.
    2. Iterate through the nums, use i, which nums[i] is the first element. And we also have l and r, which the answer is equal to nums[i] + nums[l] + nums[r]. And the answer is the closest 3 sum to target.
    3. The i is the id of the first element of the 3 sum, which 0 <= i < n; (Here n is the size of the nums). We iterate the nums use i, and let l = i+1, r = n-1;
    4. If the nums[i] + nums[l] + nums[r] < target, it means we should let 3 sum become larger, and it can be closer to the target, so here we let l = l + 1. (don't forget that the nums is ordered now!!!)
    5. if the nums[i] + nums[l] + nums[r] > target, it means we should let 3 sum become smaller.
    6. Every time we compare the 3 sum to the result we get before, and finally, we could get the final result.

    c++ code

    class Solution {
    public:
        int threeSumClosest(vector<int>& nums, int target) {
            sort(nums.begin(), nums.end());
            if (nums.size() < 3) return 0;
            int n = nums.size();
            int res = nums[n-1] + nums[n-2] + nums[n-3];
            int l, r, t;
            for (int i = 0; i < n; i++) {
                l = i+1, r = n-1;
                while (l < r) {
                    t = nums[i] + nums[l] + nums[r];
                    if (abs(res-target) > abs(t-target)) {
                        res = t;
                    }
                    if (t == target) return t;
                    if (t < target) l+=1;
                    else r-=1;
                }
            }
            return res;
        }
    };
    

    Complexity Analysis
    The outer for loop use O(n) to iterate all element in nums, and inner while loop is O(n), we use 2 pointers here, so the final complexity is O(n^2).


Log in to reply
 

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