LeetCode|LeetCode 16. 3Sum Closest(最接近的三数之和 java)
给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数,使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。
示例:
【LeetCode|LeetCode 16. 3Sum Closest(最接近的三数之和 java)】给定数组 nums = [-1,2,1,-4], 和 target = 1.思路:
与 target 最接近的三个数的和为 2. (-1 + 2 + 1 = 2).
- 比15题更加简单,确定一个数,然后用头尾双指针确定另两个数即可
- 先使用
Arrays.sort()
方法进行排序,使头尾指针有意义
public int threeSumClosest(int[] nums, int target) {
Arrays.sort(nums);
int res= Integer.MAX_VALUE,res1 = 0,add,temp,flag= Integer.MAX_VALUE;
for (int k = 0;
k < nums.length;
k++) {
int i = k + 1, j = nums.length - 1;
while (i < j) {
temp = nums[k] +nums[i] + nums[j];
add = target -temp;
flag = Math.abs(add);
if (flag < res) {
res = flag;
res1 = temp;
}
if (add > 0)
i++;
else
j--;
}
}
return res1;
}
总结:
- 数组题都较为考验对循环的掌握能力,用最小的代价获取最关键的信息
- 使用头尾双指针需要注意没有漏过一些答案组合
- 在没有思路时,使用
Arrays.sort()
进行排序,能提供新的可行道路
推荐阅读
- 【Leetcode/Python】001-Two|【Leetcode/Python】001-Two Sum
- leetcode|leetcode 92. 反转链表 II
- 二叉树路径节点关键值和等于目标值(LeetCode--112&LeetCode--113)
- LeetCode算法题-11.|LeetCode算法题-11. 盛最多水的容器(Swift)
- LeetCode(03)Longest|LeetCode(03)Longest Substring Without Repeating Characters
- 视频搬运工小赵-10#16.04元
- VM|VM ware 的 harbor 私有仓库搭建 (Ubuntu16.04)
- Leetcode|Leetcode No.198打家劫舍
- 季節
- 生存实况之1.16.1原版生存