15. 三数之和

三数之和

以一个元素为起点，双指针遍历左右元素

+ (NSArray*)threeSum:(NSArray *)nums {
    
    if (nums == nil) return nil;
    
    NSMutableArray *list = [NSMutableArray array];
    
    if (nums.count < 3) return list;
    
    nums = [nums sortedArrayUsingComparator:^NSComparisonResult(NSNumber *  _Nonnull obj1, NSNumber*  _Nonnull obj2) {
        return obj1.intValue - obj2.intValue;
    }];
    
    for (NSInteger i = 0; i < nums.count - 3; i++) {
        
        if (i > 0 && [nums[i] isEqualToNumber:nums[i-1]]) continue;
        
        NSNumber *num = nums[i];
        NSInteger left = i + 1, right = nums.count - 1, remin = -(num.intValue);
        
        
        while (left < right) {
            
            NSNumber *leftVal = nums[left], *rightVal = nums[right];
            
            NSInteger leftValue = leftVal.integerValue, rightvalue = rightVal.integerValue, totalValue = leftValue + rightvalue;
            
            if (totalValue == remin) {
                
                NSMutableArray *sub = [NSMutableArray array];
                [sub addObject:num];
                [sub addObject:nums[left]];
                [sub addObject:nums[right]];
                [list addObject:sub];
                while (left < right && [nums[left] isEqualToNumber:nums[left+1]]) left++;
                while (left < right && [nums[right] isEqualToNumber:nums[right-1]]) right--;
                left++;
                right--;
                
            } else if (totalValue < remin) {
                left++;
            } else {
                right--;
            }
        }
    }
    
    return list;
}

最接近三数之和

题解: 首先排序，一个指针从左到右遍历，后续接双针向中间逼近

 func threeSumClosest(_ nums: [Int], _ target: Int) -> Int {
        
        let sortNums = nums.sorted(by: <)
        var best = 10000000
        
        let n = sortNums.count
        
        for i in 0 ..< n {
            // 保证和上一次枚举的元素不相等
            if i > 0 && sortNums[i] == sortNums[i-1] {
                continue
            }
            
            // 双指针
            var left = i + 1, right = n - 1
            while left < right {
               let sum = sortNums[i] + sortNums[left] + sortNums[right]
               if sum == target {
                    return target
               }
            
                if abs(sum - target) < abs(best - target) {
                    best = sum
                }
                
                if sum > target {
                    var right0 = right - 1
                    while left < right0 && sortNums[right] == sortNums[right0] {
                        right0 -= 1
                    }
                    right = right0
                } else {
                    var left0 = left + 1
                    while left0 < right && sortNums[left0] == sortNums[left] {
                        left0 += 1
                    }
                    left = left0
                }
            }
        }
        return best
    }