leetcode 日记 3sumclosest java
2024-10-17 02:15:12
思路一为遍历：
public int thirdSolution(int[] nums, int target) {
int result = nums[0] + nums[1] + nums[2];
Arrays.sort(nums);
for (int i = 0; i < nums.length - 2; i++) {
int start = i + 1, end = nums.length - 1;
while (start < end) {
int tmp = nums[i] + nums[start] + nums[end];
if (tmp < target) {
start++;
}
if (tmp > target) {
end--;
}
if (tmp == target) {
return tmp;
}
if (Math.abs(tmp - target) < Math.abs(result - target)) {
result = tmp;
}
}
}
return result;
}
整体思路二为将threeSum将为twoSum即可
public int solution(int[] nums, int target) {
if (nums.length == 3) {
return nums[0] + nums[1] + nums[2];
} else {
Arrays.sort(nums);
int r = 10000;//此两处10000为省事而设，如果严谨应该大致找到其中的一个较大距离
int distance = 10000;
for (int i = 0; i < nums.length; i++) {
int[] temarray = new int[nums.length - 1];
System.arraycopy(nums, 0, temarray, 0, i);
System.arraycopy(nums, i + 1, temarray, i, nums.length - i - 1);
int tem = twoSumClosest(temarray, target - nums[i]) + nums[i];
int temdistance = tem - target;
if (temdistance < 0) {
temdistance = -temdistance;
} else if (temdistance == 0) {
return tem;
}
if (temdistance < distance) {
r = tem;
distance = temdistance;
}
}
return r;
}
}
private int twoSumClosest(int[] nums, int target) {
int l = 0, r = nums.length - 1;
int min = nums[r] + nums[l];
int distance;
if (min - target > 0) {
distance = min - target;
} else {
distance = target - min;
}
while (l < r) {
if (nums[l] + nums[r] == target)
return nums[l] + nums[r];
if (nums[l] + nums[r] < target) {
if (target - (nums[l] + nums[r]) < distance) {
min = nums[l] + nums[r];
distance = target - (nums[l] + nums[r]);
}
l++;
continue;
}
if (nums[l] + nums[r] > target) {
if ((nums[l] + nums[r]) - target < distance) {
min = nums[l] + nums[r];
distance = (nums[l] + nums[r]) - target;
}
r--;
continue;
}
}
return min;
}
本质上讲两种思路没有区别
最新文章
- GJM ： 【技术干货】给The Lab Renderer for Unity中地形添加阴影
- linux命令学习（一）—— 文件和目录管理命令
- Genesis不能运行Perl编译后的脚本
- jQuery学习笔记（一）：入门【转】
- win server 2008配置ftp无法登陆问题的解决办法
- php用jquery-ajax上传多张图片限制图片大小
- CUBRID学习笔记23 关键字列表
- python一个注意的地方
- Dynamically loading an external JavaScript or CSS file
- Struts2.x jsp页面无法使用jsp:forward跳转到action
- Entity Framework 杂碎
- Qt 图形特效(Graphics Effect)介绍
- margin的简单应用
- Android Annotations(2)
- redis 安装实战(10步完成安装)
- Docker学习（转）
- CentOS 7.4nginx配置SSL
- 同事在使用shiro后遇到的异常
- Mysql 性能优化7【重要】sql语句的优化 浅谈MySQL中优化sql语句查询常用的30种方法(转)
- python的动态性和_slot_