<span style="color:#ff4635">敬请关注博客，后期不断更新优质博文，谢谢</span>
package leetcode.T016_threeSumClosest;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
/**
* @Title: Solution.java
* @Package leetcode.T016_threeSumClosest
* @Description: TODO
* @author zhouzhixiang
* @date 2017-6-7 下午9:05:41
* @version V1.0
*/
public class Solution {
/**
* <pre>
* 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. You
* may assume that each input would have exactly one solution.
*
* 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).
*
* 题目大意：
* 给定包含n个整数数组S，找到S中的三个整数，从而使之和最接近给定的数。
* 返回三个整数的总和。你可以假设每个输入将有一个确切的解决。
*
* 解题思路：
* First:让所有非重复的三个元素之和减去输入值获取到他们之间的绝对值，绝对值最小的那一组元素和即为最终结果
* </pre>
*
* @param nums
* @param target
* @return
*/
public static void main(String[] args) {
int[] arr = { -1, 2, 1, 0 };
int s = 1;
int l = new Solution().threeSumClosest2(arr, s);
System.out.println(l);
}
/**
* @Title: threeSumClosest
* @Description: zhouzhixiang-First:麻烦，头脑短路
* @param @param arr
* @param @param s
* @param @return
* @return int
* @throws
*/
public int threeSumClosest(int[] arr, int s) {
if (arr == null || arr.length == 0) {
return 0;
}
if (s > Integer.MAX_VALUE || s < Integer.MIN_VALUE) {
return 0;
}
int sum = 0;
String sums = "";
int result = 0;
Map<Integer, Integer> map = new HashMap<Integer, Integer>();
for (int i = 0; i < arr.length - 2; i++) {
for (int j = i + 1; j < arr.length - 1; j++) {
for (int z = j + 1; z < arr.length; z++) {
sum = arr[i] + arr[j] + arr[z];
// sums += "("+arr[i]+","+arr[j]+","+arr[z]+"),";
// 记录下三数之和与输入值的差的绝对值
int abs = Math.abs(sum - s);
// 放入Map集合中,key对应的是两者之差的绝对值，value对应的是三元素之和
map.put(abs, sum);
}
}
}
// 设置个最小数值，
int min = Integer.MAX_VALUE;
// 通过循环遍历加判断获取到最小的key，key既是两者之差最小值，则value即为最接近所输数值的三元素之和
for (Map.Entry<Integer, Integer> m : map.entrySet()) {
if (min > m.getKey()) {
min = m.getKey();
result = m.getValue();
}
}
return result;
}
/**
* @Title: threeSumClosest2
* @Description: zhouzhixiang-Second：较为简便
* @param @param arr
* @param @param s
* @param @return
* @return int
* @throws
*/
public int threeSumClosest2(int[] arr, int s) {
if (arr == null || arr.length == 0) {
return 0;
}
if (s > Integer.MAX_VALUE || s < Integer.MIN_VALUE) {
return 0;
}
// 设置个最小数值，
int min = Integer.MAX_VALUE;
// 设置三元素之和
int sum = 0;
// 输出结果
int result = 0;
Map<Integer, Integer> map = new HashMap<Integer, Integer>();
for (int i = 0; i < arr.length - 2; i++) {
for (int j = i + 1; j < arr.length - 1; j++) {
for (int z = j + 1; z < arr.length; z++) {
sum = arr[i] + arr[j] + arr[z];
// 记录下三数之和与输入值的差的绝对值
int abs = Math.abs(sum - s);
if (min > abs) {
min = abs;
result = sum;
}
}
}
}
return result;
}
/**
* @Title: threeSumClosest3
* @Description: 参考：值得借鉴：比较简便
* @param @param nums
* @param @param target
* @param @return
* @return int
* @throws
*/
public int threeSumClosest3(int[] nums, int target) {
// 记录最小的差值
long minDiff = Long.MAX_VALUE;
// 记录最小差值对应的三个整数和和
long result = 0;
// 每次求得的差值
long diff;
// 每次求得的三个整数的和
long sum;
// 先对数组进行排序
Arrays.sort(nums);
// i表示假设取第i个数作为结果
for (int i = 0; i < nums.length - 2; i++) {
// 第二个数可能的起始位置
int j = i + 1;
// 第三个数可能是结束位置
int k = nums.length - 1;
while (j < k) {
// 求当前三个数的和
sum = nums[j] + nums[k] + nums[i];
// 当前和与目标和之间的差值
diff = Math.abs(target - sum);
// 差值为0就直接返回
if (diff == 0) {
return (int) sum;
}
// 如果当前的差值比之前记录的差值小
if (diff < minDiff) {
// 更新最小的差值
minDiff = diff;
// 更新最小差值对应的和
result = sum;
// 以上的设置在下一次元素处理时生效
}
// 和大于target
if (sum > target) {
k--;
}
// 和小于target
else {
j++;
}
}
}
return (int) result;
}
}
欢迎加入Java猿社区
