a Simple way with O(n2)


  • 0
    V
    class Solution {
        public int threeSumClosest(int[] nums, int target) {
            int min = Integer.MAX_VALUE;
            Map<Integer, Integer> map = new HashMap<>();
            Arrays.sort(nums);
            int i = 0;
            while (i < nums.length - 2) {
                int j = i + 1;
                int k = nums.length - 1;
                while (j < k) {
                    int sum = nums[i] + nums[j] + nums[k];
                    if (Math.abs(sum-target) < min) {
                            min = Math.abs(sum-target);
                            map.put(min,sum);
                    } 
                    if (sum >= target) while(nums[k] == nums[--k] && k > j);
                    if (sum <= target) while(nums[j] == nums[++j] && j < k);
                }
                while(nums[i] == nums[++i] && i < nums.length - 2);
            } 
            return map.get(min);
        }
    }
    

Log in to reply
 

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