LeetCode – 3Sum Closest (Java)

Dada una matriz S de n enteros, encuentre tres enteros en S tales que la suma esté más cerca de un número dado, objetivo. Devuelve la suma de los tres números enteros. Puede suponer que cada entrada tendría exactamente una solución.

For example, given array S = {-1 2 1 -4}, and target = 1. 
The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

Análisis

Este problema es similar a 2 Sum. Este tipo de problema puede resolverse utilizando un enfoque similar, es decir, dos punteros de izquierda y derecha.

Solución Java

public int threeSumClosest(int[] nums, int target) {
    int min = Integer.MAX_VALUE;
	int result = 0;
 
	Arrays.sort(nums);
 
	for (int i = 0; i < nums.length; i++) {
		int j = i + 1;
		int k = nums.length - 1;
		while (j < k) {
			int sum = nums[i] + nums[j] + nums[k];
			int diff = Math.abs(sum - target);
 
			if(diff == 0) return sum;
 
			if (diff < min) {
				min = diff;
				result = sum;
			}
			if (sum <= target) {
				j++;
			} else {
				k--;
			}
		}
	}
 
	return result;
}

La complejidad del tiempo es O (n ^ 2).