力扣题目学习笔记(OC + Swift)16. 最接近的三数之和

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满足 a+b+c≈target。当第二重循环往后枚举一个元素 b′ 时，由于 b′>b，那么满足 a+b′+c′≈target的 c′一定有 c′<c, c′在数组中一定出现在 c 的左侧。也就是说，我们可以从小到大枚举 b，同时从大到小枚举 c，即第二重循环和第三重循环实际上是并列的关系。

因此，我们就可以保持第二重循环不变，而将第三重循环变成一个从数组最右端开始向左移动的指针，这个思想就是「双指针」。每次遍历我们记录一个结果，和target比较，随着循环进行，我们的结果必然无限接近这个target值。

优化点：
1.每层遍历注意去除相邻重复的数字
2.若三数之和等于target，则直接返回，因为没有比相等更接近的了[😂]
3.设 i<cnt-2 && s = nums[i] + nums[i+1] + nums[i+2]。如果 s > target，由于数组已经排序，后面无论怎么选，选出的三个数的和不会比 s 还小，所以不会找到比 s 更优的答案了。所以只要 s > target，就可以直接 break 外层循环了。在 break 前判断 s 是否离 target 更近，如果更近，那么更新 best 为 s。
4.设 cnt > 1 && i<cnt-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.count
        
        var result: Int = Int(1e7)
        
        let updateValue = {(sum:Int) in
            if sum == 2938 {
                print("")
            }
            
            if abs(sum-target) < abs(result-target) {
                result = sum;
            }
        }
        
        for i in 0..<cnt {
            if i>0 && sortedNum[i] == sortedNum[i-1] {
                continue
            }
            
            //由于有序，后面无论怎么选，选出的三个数的和不会比 s 还小
            if i<cnt-2 && sortedNum[i]+sortedNum[i+1]+sortedNum[i+2]>=target {
                updateValue(sortedNum[i]+sortedNum[i+1]+sortedNum[i+2]);
                break
            }
            
            //由于数组已经排序，nums[i] 加上后面任意两个数都不超过 s，所以下面的双指针就不需要跑了，但i增大后存在可能，因此继续外层
            if cnt > 1 && i<cnt-2 && sortedNum[i] + sortedNum[cnt-2] + sortedNum[cnt-1] < target {
                updateValue(sortedNum[i]+sortedNum[cnt-2]+sortedNum[cnt-1]);
                continue
            }
            
            var j=i+1, k=cnt-1
            while j < k {
                let s = sortedNum[i] + sortedNum[j] + sortedNum[k]
                if s == target {
                    return target
                }
                
                updateValue(s);
                
                if s < target {
                    var j0 = j+1;
                    while j0<cnt && sortedNum[j0] == sortedNum[j0-1] {
                        j0 += 1
                    }
                    j = j0
                }else {
                    var k0 = k-1
                    while k0 > 0 && sortedNum[k0] == sortedNum[k0+1] {
                        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 i=0; i<cnt; i++) {
        //过滤重复的部分
        if (i>0 && sortedNum[i] == sortedNum[i-1]) {
            continue;
        }
        
        //由于有序，后面无论怎么选，选出的三个数的和不会比 s 还小
        if (i<cnt-2 && [sortedNum[i] integerValue] +[sortedNum[i+1] integerValue] + [sortedNum[i+2] integerValue] >= target) {
            updateValue([sortedNum[i] integerValue]+[sortedNum[i+1] integerValue] + [sortedNum[i+2] integerValue]);
            break;
        }
        
        //由于数组已经排序，nums[i] 加上后面任意两个数都不超过 s，所以下面的双指针就不需要跑了，但i增大后存在可能，因此继续外层
        if (cnt > 1 && i<cnt-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 j=i+1, k=cnt-1;
        while (j<k) {
            NSInteger s = [sortedNum[i] integerValue] + [sortedNum[j] integerValue] + [sortedNum[k] integerValue];
            if (s == target) {
                return s;
            }
            
            updateValue(s);
            
            if(s < target) {
                NSInteger j0 = j+1;
                //过滤重复的部分
                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[k0+1] integerValue]) {
                    k0--;
                }
                k = k0;
            }
        }
    }
    
    return result;
}