题意:
给定一列数,和一个目标数,查找这一列数中三个数的和中最接近目标数的那个和。
分析:
这道题非常好,搜索本来就是体现经典算法的操作之一,而搜索算法往往其实质在于动态的缩小搜索空间。
我们能动态的接近结果呢? ==》说明新的区间比旧的区间更靠近答案 ==》 无序的数组肯定是办不到的,因为哪哪都一样 ==》我们对数组排序,再继续分析 ==》某一个区间
left 到 right, 应该怎么动态变化呢?能不能区间的两个端点都动态变化呢? ==》说明新的区间一定比旧的区间更接近结果 ==》再结合我们已经排序了 ==》我们从和最大开始,即left right 在一头一尾, 当和大了,就减小right,当和小了,就增加left。
所以:
public class Solution { public int threeSumClosest(int[] nums, int target) { Arrays.sort(nums); int res = nums[0] + nums[1] + nums[nums.length-1]; for(int i=0; i<nums.length-2; i++){ int start = i+1; int end = nums.length-1; while(start < end){ int sum = nums[i] + nums[start] + nums[end]; if(sum == target){ return sum; }else if(sum > target){ end--; }else if(sum < target){ start++; } res = Math.abs(sum - target) < Math.abs(res - target) ? sum : res; } } return res; } }