力扣题目学习笔记(OC + Swift)15. 三数之和

15. 三数之和

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请
你返回所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。

排序 + 双指针

「不重复」且和为 0 的三元组，这个「不重复」的要求使得我们无法简单地使用三重循环枚举所有的三元组。且三重循环时间复杂度为O(n^3)，时间及空间复杂度均不满足我们使用的需求。
若我们枚举的三元组 (a,b,c) 满足a≤b≤c，保证了只有 (a,b,c)这个顺序会被枚举到，而 (b,a,c)、(c,b,a) 等等这些不会，这样就减少了重复。
可以发现，如果我们固定了前两重循环枚举到的元素 a和 b，那么只有唯一的 c满足 a+b+c=0。当第二重循环往后枚举一个元素 b′ 时，由于 b′>b，那么满足 a+b′+c′=0的 c′一定有 c′<c, c′在数组中一定出现在 c 的左侧。也就是说，我们可以从小到大枚举 b，同时从大到小枚举 c，即第二重循环和第三重循环实际上是并列的关系。

因此，我们就可以保持第二重循环不变，而将第三重循环变成一个从数组最右端开始向左移动的指针，这个思想就是「双指针」
注意每层遍历的去重。
注意第三重和第二重不能重合。

知识点：「双指针适用场景」当我们需要枚举数组中的两个元素时，如果我们发现随着第一个元素的递增，第二个元素是递减的，那么就可以使用双指针的方法，将枚举的时间复杂度从 O(n^2)降至O(n)。

总体时间复杂度：O(n^2), 排序时间复杂度为O(nlogn)，渐进抵消
空间复杂度：O(logN)

Swift

func threeSum(_ nums: [Int]) -> [[Int]] {
        let sortedNums = nums.sorted()
        
        let cnt = nums.count
        var results: [[Int]] = [[Int]]()
        
        for i in 0..<cnt {
            // 需要和上一次枚举的数不相同
            if i>0 && sortedNums[i] == sortedNums[i-1] {
                continue
            }
            
            var k = cnt-1;
            let target = -sortedNums[i]
            
            for j in i+1..<cnt {
                // 需要和上一次枚举的数不相同
                if j > i+1 && sortedNums[j] == sortedNums[j-1] {
                    continue
                }
                
                // 需要保证 b 的指针在 c 的指针的左侧
                while j<k && sortedNums[j]+sortedNums[k] > target {
                    k -= 1
                }
                
                if j == k {
                    break
                }
                
                if sortedNums[j]+sortedNums[k] == target {
                    results.append([sortedNums[i], sortedNums[j], sortedNums[k]])
                }
            }
        }

OC

-(NSArray <NSNumber *>*)threeSum:(NSArray *)nums {
    NSArray *sortedNums = [nums sortedArrayUsingComparator:^NSComparisonResult(NSNumber * obj1, NSNumber * obj2) {
        return [obj1 compare:obj2];
    }];
    
    NSMutableArray *results = @[].mutableCopy;
    
    NSInteger cnt = nums.count;
    for (NSInteger i=0; i<cnt; i++) {
        // 需要和上一次枚举的数不相同
        if (i>0 && [sortedNums[i] integerValue] == [sortedNums[i-1] integerValue]) {
            continue;
        }
        
        NSInteger target = -[sortedNums[i] integerValue];
        //定义双指针
        NSInteger k = cnt-1;
        for (NSInteger j=i+1; j<cnt; j++) {
            // 需要和上一次枚举的数不相同
            if (j>i+1 && [sortedNums[j] integerValue] == [sortedNums[j-1] integerValue]) {
                continue;
            }
            
            while (j < k && [sortedNums[j] integerValue] + [sortedNums[k] integerValue] > target) {
                k--;
            }
            
            if (j == k) {
                break;
            }
            
            if ([sortedNums[j] integerValue] + [sortedNums[k] integerValue] == target) {
                [results addObject:@[sortedNums[i], sortedNums[j], sortedNums[k]]];
            }
        }
    }
    return results;
}