//time O(NlogN)
class Solution {
    public int threeSumClosest(int[] nums, int target) {
        Arrays.sort(nums);
        int optimal = 1000000;
        for(int i = 0;i < nums.length;i++){
          int firstVal = nums[i];
          int left = i + 1, right = nums.length - 1;

          while(left < right){
            int secVal = nums[left];
            int thirdVal = nums[right];
            int sum = firstVal + secVal + thirdVal;
            if(Math.abs(sum - target) < Math.abs(optimal - target)){
              optimal = sum;
            }
            if(sum < target){
              left++;
            } else if(sum == target){
              return sum;
            } else {
              right--;
            }
          }
        }
        return optimal;
    }
}