3Sum Closest & 3Sum Smaller
2024-08-29 00:55:20
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.
Notice
You may assume that each input would have exactly one solution.
Example
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).
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[] num ,int target) {
int tempClosestSum = Integer.MAX_VALUE;
int diff = Integer.MAX_VALUE;
if(num == null || num.length < ) {
return tempClosestSum;
}
Arrays.sort(num);
for (int i = ; i < num.length - ; i++) {
if (i != && num[i] == num[i - ]) {
continue; // to skip duplicate numbers; e.g [0,0,0,0]
} int left = i + ;
int right = num.length - ;
while (left < right) {
int sum = num[left] + num[right] + num[i];
if (sum - target == ) {
return target;
} else if (sum - target < ) {
if (Math.abs(sum - target) < Math.abs(tempClosestSum - target)) {
tempClosestSum = sum;
}
left++;
} else {
if (Math.abs(sum - target) < Math.abs(tempClosestSum - target)) {
tempClosestSum = sum;
}
right--;
}
}
}
return tempClosestSum;
}
}
3Sum Smaller
Given an array of n integers nums and a target, find the number of index triplets i, j, k
with 0 <= i < j < k < n
that satisfy the condition nums[i] + nums[j] + nums[k] < target
.
For example, given nums = [-2, 0, 1, 3]
, and target = 2.
Return 2. Because there are two triplets which sums are less than 2:
[-2, 0, 1]
[-2, 0, 3] 分析:https://segmentfault.com/a/1190000003794736
解题思路和3SUM一样,也是先对整个数组排序,然后一个外层循环确定第一个数,然后里面使用头尾指针left和right进行夹逼,得到三个数的和。如果这个和大于或者等于目标数,说明我们选的三个数有点大了,就把尾指针right向前一位(因为是排序的数组,所以向前肯定会变小)。
如果这个和小于目标数,那就有right - left个有效的结果。为什么呢?因为假设我们此时固定好外层的那个数,还有头指针left指向的数不变,那把尾指针向左移0位一直到左移到left之前一位,这些组合都是小于目标数的。
public int threeSumSmaller(int[] nums, int target) {
// 先将数组排序
Arrays.sort(nums);
int cnt = ;
for (int i = ; i < nums.length - ; i++) {
int left = i + , right = nums.length - ;
while (left < right) {
int sum = nums[i] + nums[left] + nums[right];
// 如果三个数的和大于等于目标数,那将尾指针向左移
if (sum >= target) {
right--;
// 如果三个数的和小于目标数,那将头指针向右移
} else {
// right - left个组合都是小于目标数的
cnt += right - left;
left++;
}
}
}
return cnt;
}
最新文章
- Lua模块
- Visual Studio 2013 各个版本的产品密钥
- 1813. M进制数问题
- .net的垃圾回收机制简述
- bs4_3select()
- Js navigator.onLine 获取设备是否可以上网、连接网络
- .NET 中的委托
- JDBC 与ODBC的区别
- linux下使用kpartx挂载虚拟文件系统
- 上传图片,多图上传,预览功能,js原生无依赖
- 10年java过来人聊聊自己的自学、培训和工作经历
- MFC界面相关源码
- .net排坑篇:负载均衡域名转发的背后
- ROS学习笔记一(ROS的catkin工作空间)
- Selenium UI自动化测试 Selenium Automatic Testing
- Linux内核链表
- nodejs v8引擎
- InnoDB的后台线程(IO线程,master线程,锁监控线程,错误监控线程)和内存(缓冲池,重做日志缓冲池,额外内存池)
- Scrum Meeting Beta - 3
- 【BZOJ】2049: [Sdoi2008]Cave 洞穴勘测 LCT