leetcode-algorithms/src/ThreeSumClosest.java at master · anishLearnsToCode/leetcode-algorithms · GitHub

28 lines (25 loc) · 883 Bytes

// https://leetcode.com/problems/3sum-closest

// T: O(n^2)

// S: O(1)

import java.util.Arrays;

public class ThreeSumClosest {

public static void main(String[] args) {

System.out.println(threeSumClosest(new int[] {0, 2, 1, -3}, 1));

}

public static int threeSumClosest(int[] nums, int target) {

Arrays.sort(nums);

int closestSum = nums[0] + nums[1] + nums[2];

for (int i = 0 ; i < nums.length - 2 ; i++) {

for (int j = i + 1, k = nums.length - 1 ; j < k ; ) {

int sum = nums[i] + nums[j] + nums[k];

if (sum == target) return sum;

if (Math.abs(sum - target) < Math.abs(closestSum - target)) {

closestSum = sum;

}

else if (sum > target) k--;

else j++;

}

return closestSum;

}

Expand file tree