3 Sum Closest

Problem

Given an array S of n integers, find three integers in S such that the sum is closest to a given number, target. Return the sum of the three integers.

Analysis

思路,类似于 3 Sum 问题,不同之处在于寻找与target的绝对值最小的数;同样可以利用two pointers,对于 a + b + c 中的 b, c 来作为两个指针,a 为 num[i], 那么b初始值则为 num[i + 1], c初始值为num[len - 1]; 通过比较每次 a + b + c 的sum与target的大小,来确定移动b,或者移动c。

Solution

public class Solution {
/**
* @param numbers: Give an array numbers of n integer
* @param target : An integer
* @return : return the sum of the three integers, the sum closest target.
*/
public int threeSumClosest(int[] numbers,int target) {
if (numbers == null || numbers.length < 3) {
return Integer.MAX_VALUE;
}
Arrays.sort(numbers);
int diff = Integer.MAX_VALUE / 2;
int length = numbers.length;
int sign = 1;
for (int i = 0; i < length - 2; i++) {
int pl = i + 1;
int pr = length - 1;
while (pl < pr) {
int sum = numbers[i] + numbers[pl] + numbers[pr];
if (sum == target) {
return sum;
} else if (sum < target) {
if (target - sum < diff) {
diff = target - sum;
sign = -1;
}
pl++;
} else {
if (sum - target < diff) {
diff = sum - target;
sign = 1;
}
pr--;
}
}
}
return target + sign * diff;
}
}
Two Pointer - Use Math.abs() - (10ms, 78.40%)
// Use Math.abs(), two pointers
class Solution {
public int threeSumClosest(int[] numbers, int target) {
if (numbers == null || numbers.length < 3) {
return Integer.MAX_VALUE;
}
Arrays.sort(numbers);
int length = numbers.length;
int closest = Integer.MAX_VALUE / 2;
for (int i = 0; i < length - 2; i++) {
int pl = i + 1;
int pr = length - 1;
while (pl < pr) {
int sum = numbers[i] + numbers[pl] + numbers[pr];
if (sum == target) {
return sum;
} else if (sum < target) {
pl++;
} else {
pr--;
}
closest = Math.abs(sum - target) < Math.abs(closest - target) ?
sum : closest;
}
}
return closest;
}
}
Two Pointer - (11ms 65.24%) - Time O(n^2), Space O(1)
基于3Sum,别忘了,先sort这个数组。
外层i = 0, ... , nums.length - 2;内层j = i + 1, k = nums.length - 1,这样再根据nums[j] + nums[k] vs target - nums[i]的比较,来移动j或者k指针。
记录与target最小的gap,minGap;用Math.abs()进行比较,这样minGap可以保留符号,最后closest = target + minGap
class Solution {
public int threeSumClosest(int[] nums, int target) {
Arrays.sort(nums);
int closest = target;
int minGap = Integer.MAX_VALUE / 2;
for (int i = 0; i < nums.length - 2; i++) {
int j = i + 1, k = nums.length - 1;
int t = target - nums[i];
while (j < k) {
if (Math.abs(nums[j] + nums[k] - t) < Math.abs(minGap)) {
minGap = nums[j] + nums[k] - t;
}
if (nums[j] + nums[k] > t) {
k--;
} else if (nums[j] + nums[k] < t) {
j++;
} else {
// found 3sum equals target
return target;
}
}
}
closest = target + minGap;
return closest;
}
}
Last modified 3yr ago