Java O(n^2) Clean and Clear Solution


  • 3
    X
    public class Solution {
        public int threeSumClosest(int[] nums, int target) {
            Arrays.sort(nums);
            int min_diff = Integer.MAX_VALUE;
            for(int i=0; i<nums.length-2; ++i){
                int p = i+1, q = nums.length-1;
                while(p<q){
                    int diff = nums[i]+nums[p]+nums[q] - target;
                    if(diff == 0)   return target;
                    min_diff = Math.abs(diff)<Math.abs(min_diff) ? diff: min_diff;
                    if(diff>0)  --q;
                    else    ++p;
                }
            }
            return target + min_diff;
        }
    }

  • 0
    B

    that's O(n²), you are going through the array in the while loop for each element (selected by the for loop)


  • 0
    X

    Oh, thanks. I mean O(n^2)


Log in to reply
 

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