1 题目
给一个包含 n 个整数的数组 S, 找到和与给定整数 target 最接近的三元组，返回这三个数的和。
样例 1：
输入：
numbers = [2,7,11,15]
target = 3输出：
20解释：2+7+11=20
样例 2：
输入：
numbers = [-1,2,1,-4]
target = 1输出：
2解释：-1+2+1=2
挑战 时间复杂度：O(n^2) ，空间复杂度：O(1)
2 解答
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) { // write your code here int res = Integer.MAX_VALUE; // 1、当数组为空或者不满足3个的长度时返回 if (numbers == null || numbers.length < 3) { return res; } // 排序 Arrays.sort(numbers); // 初始化默认返回 res = numbers[0] + numbers[1] + numbers[2]; int gap = Math.abs(target - res); // 双指针遍历 for (int i = 0; i < numbers.length; i++) { int left = i+1; int right = numbers.length-1; while (left < right) { // 计算三个数的和 int sum = numbers[i] + numbers[left] + numbers[right]; // 如果差距比 gap 小 赋值给res int currenGap = Math.abs(target - sum); if (currenGap < gap) { res = sum; gap = currenGap; } // 如果大于那么 right-- // 如果小于那么 left ++ // 如果相等直接返回 if (sum > target) { right--; } else if (sum < target) { left++; } else { return target; } } } return res; } }
加油。