网站安全加固,铁岭房地产网站建设,网站模板 wordpress,网站建设应该注意什么16. 最接近的三数之和 给你一个长度为 n 的整数数组 nums 和 一个目标值 target。请你从 nums 中选出三个整数#xff0c;使它们的和与 target 最接近。 返回这三个数的和。 假定每组输入只存在恰好一个解。 排序 双指针
思路同15. 三数之和
简单地使用三重循环枚举所有的三…16. 最接近的三数之和 给你一个长度为 n 的整数数组 nums 和 一个目标值 target。请你从 nums 中选出三个整数使它们的和与 target 最接近。 返回这三个数的和。 假定每组输入只存在恰好一个解。 排序 双指针
思路同15. 三数之和
简单地使用三重循环枚举所有的三元组时间复杂度为O(n^3)时间及空间复杂度均不满足我们使用的需求。 若我们枚举的三元组 (a,b,c) 满足a≤b≤c保证了只有 (a,b,c)这个顺序会被枚举到而 (b,a,c)、(c,b,a) 等等这些不会这样就减少了重复。 可以发现如果我们固定了前两重循环枚举到的元素 a和 b那么只有唯一的 c满足 abc≈target。当第二重循环往后枚举一个元素 b′ 时由于 b′b那么满足 ab′c′≈target的 c′一定有 c′c, c′在数组中一定出现在 c 的左侧。也就是说我们可以从小到大枚举 b同时从大到小枚举 c即第二重循环和第三重循环实际上是并列的关系。
因此我们就可以保持第二重循环不变而将第三重循环变成一个从数组最右端开始向左移动的指针这个思想就是「双指针」。每次遍历我们记录一个结果和target比较随着循环进行我们的结果必然无限接近这个target值。
优化点 1.每层遍历注意去除相邻重复的数字 2.若三数之和等于target则直接返回因为没有比相等更接近的了[] 3.设 icnt-2 s nums[i] nums[i1] nums[i2]。如果 s target由于数组已经排序后面无论怎么选选出的三个数的和不会比 s 还小所以不会找到比 s 更优的答案了。所以只要 s target就可以直接 break 外层循环了。在 break 前判断 s 是否离 target 更近如果更近那么更新 best 为 s。 4.设 cnt 1 icnt-2 s nums[i] nums[n-2] nums[n-1]。如果 s target由于数组已经排序nums[i] 加上后面任意两个数都不超过 s所以下面的双指针就不需要跑了无法找到比 s 更优的答案。但是后面还有更大的 nums[i]可能找到一个离 target 更近的三数之和所以还需要继续枚举continue 外层循环。在 continue 前判断 s 是否离 target 更近如果更近那么更新 best 为 s。
知识点「双指针适用场景」当我们需要枚举数组中的两个元素时如果我们发现随着第一个元素的递增第二个元素是递减的那么就可以使用双指针的方法将枚举的时间复杂度从 O(n^2)降至O(n)。
总体时间复杂度O(n^2), 排序时间复杂度为O(nlogn)渐进抵消 空间复杂度O(logN)
Swift
func threeSumClosest(_ nums: [Int], _ target: Int) - Int {let sortedNum nums.sorted()let cnt sortedNum.countvar result: Int Int(1e7)let updateValue {(sum:Int) inif sum 2938 {print()}if abs(sum-target) abs(result-target) {result sum;}}for i in 0..cnt {if i0 sortedNum[i] sortedNum[i-1] {continue}//由于有序后面无论怎么选选出的三个数的和不会比 s 还小if icnt-2 sortedNum[i]sortedNum[i1]sortedNum[i2]target {updateValue(sortedNum[i]sortedNum[i1]sortedNum[i2]);break}//由于数组已经排序nums[i] 加上后面任意两个数都不超过 s所以下面的双指针就不需要跑了但i增大后存在可能因此继续外层if cnt 1 icnt-2 sortedNum[i] sortedNum[cnt-2] sortedNum[cnt-1] target {updateValue(sortedNum[i]sortedNum[cnt-2]sortedNum[cnt-1]);continue}var ji1, kcnt-1while j k {let s sortedNum[i] sortedNum[j] sortedNum[k]if s target {return target}updateValue(s);if s target {var j0 j1;while j0cnt sortedNum[j0] sortedNum[j0-1] {j0 1}j j0}else {var k0 k-1while k0 0 sortedNum[k0] sortedNum[k01] {k0 - 1}k k0}}}return result}OC
-(NSInteger)threeSumClosest:(NSArray *)nums target:(NSInteger)target {if (nums.count 3) {return 0;}//先排序NSArray *sortedNum [nums sortedArrayUsingComparator:^NSComparisonResult(id _Nonnull obj1, id _Nonnull obj2) {return [obj1 compare:obj2];}];NSInteger cnt sortedNum.count;__block NSInteger result 1e7;void (^updateValue)(NSInteger) ^(NSInteger sum) {if (labs(sum - target) labs(result-target)) {result sum;}};//开始遍历for (NSInteger i0; icnt; i) {//过滤重复的部分if (i0 sortedNum[i] sortedNum[i-1]) {continue;}//由于有序后面无论怎么选选出的三个数的和不会比 s 还小if (icnt-2 [sortedNum[i] integerValue] [sortedNum[i1] integerValue] [sortedNum[i2] integerValue] target) {updateValue([sortedNum[i] integerValue][sortedNum[i1] integerValue] [sortedNum[i2] integerValue]);break;}//由于数组已经排序nums[i] 加上后面任意两个数都不超过 s所以下面的双指针就不需要跑了但i增大后存在可能因此继续外层if (cnt 1 icnt-2 [sortedNum[i] integerValue] [sortedNum[cnt-2] integerValue] [sortedNum[cnt-1] integerValue] target) {updateValue([sortedNum[i] integerValue][sortedNum[cnt-2] integerValue][sortedNum[cnt-1] integerValue]);continue;}NSInteger ji1, kcnt-1;while (jk) {NSInteger s [sortedNum[i] integerValue] [sortedNum[j] integerValue] [sortedNum[k] integerValue];if (s target) {return s;}updateValue(s);if(s target) {NSInteger j0 j1;//过滤重复的部分while (j0 cnt [sortedNum[j0] integerValue] [sortedNum[j0-1] integerValue]) {j0;}j j0;}else {NSInteger k0 k-1;while (k0 0 [sortedNum[k0] integerValue] [sortedNum[k01] integerValue]) {k0--;}k k0;}}}return result;
}
