题目
给你一个长度为 n 的整数数组 nums 和 一个目标值 target。请你从 nums 中选出三个整数,使它们的和与 target 最接近。
返回这三个数的和。
假定每组输入只存在恰好一个解。
示例 1:
输入:nums = [-1,2,1,-4], target = 1
输出:2
解释:与 target 最接近的和是 2 (-1 + 2 + 1 = 2) 。
示例 2:
输入:nums = [0,0,0], target = 1
输出:0
提示:
3 <= nums.length <= 1000
-1000 <= nums[i] <= 1000
-104 <= target <= 104
Related Topics
- 数组
- 双指针
- 排序
代码
基本思路是首先对数组进行排序,然后遍历数组中的每个元素作为三个数中的第一个数(记作nums[i]),使用双指针法来寻找后面两个数(记作nums[l]和nums[r]),使得这三个数的和尽可能接近目标值target。
public class Solution {
public int threeSumClosest(int[] nums, int target) {
// 1. 排序,默认升序排列
nums = Arrays.stream(nums).sorted().toArray();
System.out.println("nums = " + Arrays.toString(nums));
int len= nums.length, result = 99999;
// 2. 遍历数组,固定数 i
for (int i = 0; i < len; i++) {
// 3. 定义双指针,左指针 l=i+1,右指针 r=len-1
int l = i + 1, r = len - 1;
// 4. 双指针搜索,求和
while (l < r) {
int sum = nums[i] + nums[l] + nums[r];
// 5. 与目标值比较
// a.相等,直接return
if (sum == target) {
return sum;
}
// 6. 需要一个temp记录当前的差值
if (Math.abs(sum - target) < Math.abs(result - target)) {
result = sum;
}
// b.更小,则需要更大
if (sum < target){
l++;
}
// c.更大,则需要更小
else {
r--;
}
}
}
return result;
}
}
优化思路
解题步骤:
- 排序
- 遍历数组
- 双指针搜索
- 求和比较
时间复杂度分析:
- 排序:使用
Arrays.stream(nums).sorted().toArray()
对数组进行排序。这部分的时间复杂度是O(n log n)
; - 遍历数组:使用一个for循环。这部分的时间复杂度是
O(n)
; - 双指针遍历:遍历次数为i+1→n,外嵌一个for循环。因此时间复杂度为
O(n^2)
; - 求和比较的时间复杂度也是
O(n)
;
因此,整体时间复杂度=O(n^2)
优化方向:
1.减少重复遍历次数
2.优化排序算法
public class Solution {
public int threeSumClosest(int[] nums, int target) {
int len= nums.length, result = 99999;
// 1. 排序,默认升序排列
// 优化2:排序算法
sort(nums, 0, len-1);
System.out.println("nums = " + Arrays.toString(nums));
// 2. 遍历数组,固定数 i
for (int i = 0; i < len; i++) {
// 优化1:减少重复遍历的次数
if (i > 0 && nums[i] == nums[i - 1]) {
continue;
}
// 3. 定义双指针,左指针 l=i+1,右指针 r=len-1
int l = i + 1, r = len - 1;
// 4. 双指针搜索,求和
while (l < r) {
int sum = nums[i] + nums[l] + nums[r];
// 5. 与目标值比较
// a.相等,直接return
if (sum == target) {
return sum;
}
// 6. 需要一个temp记录当前的差值
if (Math.abs(sum - target) < Math.abs(result - target)) {
result = sum;
}
// b.更小,则需要更大
if (sum < target){
l++;
}
// c.更大,则需要更小
else {
r--;
}
}
}
return result;
}
public void sort(int[] nums,int start,int end){
if (start<end){
int p = partition(nums,start,end);
sort(nums,start,p-1);
sort(nums,p+1,end);
}
}
public int partition(int[] nums,int start,int end){
int pivot = nums[end];
int pi = start;
for (int i = start; i < end; i++) {
if (nums[i] <= pivot){
swap(nums,pi,i);
pi++;
}
}
swap(nums,pi,end);
return pi;
}
public void swap(int[] nums,int i,int j){
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}