Sharing my O(n^2) solution


  • 0
    Z
    int threeSumClosest(vector<int> &num, int target) {
        int result = INT_MAX - 1;
        sort(num.begin(), num.end());
        for(int i = 0; i < num.size();){
            int start = i + 1;
            int end = num.size() - 1;
            while(start < end){
                int sum = num[i] + num[start] + num[end];
                if(sum == target){
                    return target;
                }
                else if(sum > target){
                    result = abs(sum - target) < abs(result - target) ? sum : result;
                    end--;
                }
                else{
                    result = abs(sum - target) < abs(result - target) ? sum : result;
                    start++;
                }
            }
            int iNum = num[i];
            while(i < num.size() && num[i] == iNum){
                i++;
            }
        }
        return result;
    }
    

    This solution is straightforward and has similar idea with 3sum. If you can solve 3sum but fail this problem, just review your 3sum code then you will make it.

    Please notice the first line: int result = INT_MAX - 1; If I change it to int result = INT_MAX, the result is wrong. Anybody have any idea why this happens?


  • 0
    W

    You can init result to be num[0] + num[1] + num[2].

    The problem of INTMAX-1 or INTMAX is because result - target may overflow


  • 0
    Z

    Thank you for your answer.

    Actually I think initializing result to be num[0] + num[1] + num[2] is not a good idea because there is no guarantee the size of num is larger than 3.

    And INT_MAX - 1 works but INT_MAX doesn't work. I think the reason is related to abs() but not sure.


  • 0
    W

    .... You will need to check n > 3 at first place in your code.

    In theory , the result can actually be larger than INTMAX , so it is wrong to init result as INTMAX.
    Initing result as INTMAX or INTMAX-1 means making an assumption that there is a triple adds up to that value, which is wrong...


  • 0
    Z

    umm..Yeah I think now I know your idea. It's correct. Thanks for sharing.

    But I am still wondering why INTMAX is wrong while INTMAX - 1 is correct...


  • 0
    S

    As for these statements
    "int iNum = num[i];
    while(i < num.size() && num[i] == iNum){
    i++;
    }
    "
    why add a iNum and test it ? I can't understand


Log in to reply
 

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