网站建设与维护制度,云南网站开发公司,wordpress首页筛选,把手机的视频生成链接题目#xff1a;
给你一个长度为 n 的整数数组 nums 和 一个目标值 target。请你从 nums 中选出三个整数#xff0c;使它们的和与 target 最接近。
返回这三个数的和。
假定每组输入只存在恰好一个解。 解法一#xff08;排序双指针#xff09;#xff1a;
题目要求找…题目
给你一个长度为 n 的整数数组 nums 和 一个目标值 target。请你从 nums 中选出三个整数使它们的和与 target 最接近。
返回这三个数的和。
假定每组输入只存在恰好一个解。 解法一排序双指针
题目要求找到与目标值 target 最接近的三元组这里的「最接近」即为差值的绝对值最小。我们可以考虑直接使用三重循环枚举三元组找出与目标值最接近的作为答案时间复杂度为 O(N^3)。然而本题的 N 最大为 1000会超出时间限制。
我们首先枚举第一个元素 a1对于剩下的两个元素 a2和 a3希望它们的和最接近target−a1。对于 a2 和 a3如果它们在原数组中枚举的范围既包括下标的范围也包括元素值的范围没有任何规律可言那么我们还是只能使用两重循环来枚举所有的可能情况。因此我们可以考虑对整个数组进行升序排序这样一来 假设数组的长度为 n我们先枚举 a1它在数组中的位置为 i 为了防止重复枚举我们在位置 [i1,n) 的范围内枚举 a2 和 a3。
当我们知道了a2和a3可以枚举的下标范围并且知道这一范围对应的数组元素是有序升序的那么我们是否可以对枚举的过程进行优化呢
借助双指针对枚举的过程进行优化我们用a2和a3作为双指针初始时a2指向位置i1即左边界a3指向位置n-1即右边界。在每一步枚举过程中我们采用a1a2a3来更新答案并且 如果 a1a2a3≥target那么就将 a3 向左移动一个位置 如果 a1a2a3target那么就将 a2 向右移动一个位置。
这是为什么呢我们对 a1a2a3≥target的情况进行详细的分析
如果a1a2a3≥target并且我们知道a2和a3这个范围是按照升序排列的那么如果a3不变而移动a2向右那么a1a2a3的值就会不断地增加显然就不会成为最接近target的值了。因此我们可以知道在固定a3的情况下此时的a2就可以得到一个最接近target的值了那么我们以后就不用再考虑a3了就可以将a3向左移动一个位置。
同样地a1a2a3target 时如果a2不变而a3向左移动那么a1a2a3的值就会不断地减小显然就不会成为最接近target的值了。因此我们可以知道固定了a2的情况下此时的a3就可以得到一个最接近target的值那么我们以后就不用再考虑a2了就可以将a2向右移动一个位置。
实际上a2和a3就表示我们当前选择的数的范围而每一次枚举的过程中我们尝试边界上的两个元素根据它们与target的值的关系选择【抛弃】左边界的元素还是右边界的元素从而减少了枚举的范围。这种思路与【盛最多水的容器】中的双指针解法也是类似的。当我们枚举a1,a2,a3 中任意元素并移动指针时可以直接将其移动到下一个与这次枚举得到的不相同的元素减少枚举的次数如下代码为
class Solution {
public:int threeSumClosest(vectorint nums, int target) {sort(nums.begin(), nums.end());int n nums.size();int best 1e7;// 根据差值的绝对值来更新答案auto update [](int cur) {if (abs(cur - target) abs(best - target)) {best cur;}};// 枚举 afor (int i 0; i n; i) {// 保证和上一次枚举的元素不相等if (i 0 nums[i] nums[i - 1]) {continue;}// 使用双指针枚举 b 和 cint j i 1, k n - 1;while (j k) {int sum nums[i] nums[j] nums[k];// 如果和为 target 直接返回答案if (sum target) {return target;}update(sum);if (sum target) {// 如果和大于 target移动 c 对应的指针int k0 k - 1;// 移动到下一个不相等的元素while (j k0 nums[k0] nums[k]) {--k0;}k k0;} else {// 如果和小于 target移动 b 对应的指针int j0 j 1;// 移动到下一个不相等的元素while (j0 k nums[j0] nums[j]) {j0;}j j0;}}}return best;}
};
时间复杂度O(N2)其中 N 是数组 nums 的长度。我们首先需要 O(NlogN) 的时间对数组进行排序随后在枚举的过程中使用一重循环 O(N) 枚举 a双指针 O(N) 枚举 b 和 c故一共是 O(N2)。
空间复杂度O(logN)。排序需要使用 O(logN) 的空间。然而我们修改了输入的数组 nums在实际情况下不一定允许因此也可以看成使用了一个额外的数组存储了 nums 的副本并进行排序此时空间复杂度为 O(N)。
下面代码是笔者在编程时所写的虽然时间复杂度没有超限但是相比上面代码在时间复杂度上面仍然是消耗时间比较大的但是空间复杂度上面比上面代码占用消耗是较小的。其中第二层循环中思路也是如果和小于target则移动a2向右移动进入下一次循环如果和大于target则移动a3向左移动执行while循环实现原理通过增加条件判断语句使得双指针左边界指针、右边界指针两个指针朝着相遇的方向进行移动减少时间复杂度防止重复遍历但是阅读理解代码起来较为复杂同样是作为正确的解决思路与上面方法进行对比如下为笔者代码
class Solution {
public:int threeSumClosest(vectorint nums, int target) {//定义输出结果result值int min_value 1000000, lengthnums.size();int result0;//将nums数组由小到大重新进行排序sort(nums.begin(), nums.end());//循环遍历查找满足条件要求的结果for(int a10; a1length-2; a1){if(a11 nums[a1]nums[a1-1]){continue;}for(int a2a11; a2length-1;a2){if(a2a11 nums[a2]nums[a2-1]){continue;}int a3 length-1;//如果和小于target则移动a2向右移动进入下一层循环if(nums[a1]nums[a2]nums[a3]target){resultmin_valueabs(nums[a1]nums[a2]nums[a3]-target)?(nums[a1]nums[a2]nums[a3]):result;min_value min(abs(nums[a1]nums[a2]nums[a3]-target), min_value);continue;}while(a2a3){if(nums[a1]nums[a2]nums[a3]target){resultmin_valueabs(nums[a1]nums[a2]nums[a3]-target)?(nums[a1]nums[a2]nums[a3]):result;min_value min(abs(nums[a1]nums[a2]nums[a3]-target), min_value);resultmin_valueabs(nums[a1]nums[a2]nums[a31]-target)?(nums[a1]nums[a2]nums[a31]):result;min_value min(abs(nums[a1]nums[a2]nums[a31]-target), min_value);break;}//如果和大于target则移动a3向左移动执行while循环else{resultmin_valueabs(nums[a1]nums[a2]nums[a3]-target)?(nums[a1]nums[a2]nums[a3]):result;min_value min(abs(nums[a1]nums[a2]nums[a3]-target), min_value);a3--;}}}}return result;}
};
笔者小记
1、借助双指针对枚举的过程进行优化降低多重循环导致的时间复杂度。对于本题时间复杂度可由O(N^3)降低至O(N^2)。
