前言

一日不学习，恐落后于世界久矣。

最近有朋友面试，面试一些简单的算法，多了不说，总结如下。

1、判断整数数组中有没有随机三个数之和等于一个已知数

看到这个题目，我简单粗暴的想起了三层for循环，需要考虑的是三层for循环里的数，每层的数都不能是一样的，于是写出了这样的方法。

- (BOOL)seekRandomThreeElementSum:(NSInteger)sum Arr:(NSArray *)array {
    NSInteger b,c,d,i,j,k;
    for (i = 0; i < array.count; i ++) {
        b = [array[i] integerValue];
        for (j = 0 ; j < array.count; j ++) {
            if (j != i) {//保证外层循环的数和本层循环不一样
                c = [array[j] integerValue];
                for (k = 0; k < array.count; k ++) {
                    if (k != i && k != j) {//保证外层循环的数和本层循环不一样
                        d = [array[k] integerValue];
                        if (b + c + d == sum) {
                            NSLog(@"have the sum");
                            return YES;
                        }
                    }
                }
            }
        }
    }
    NSLog(@"have not the sum");
    return NO;
}

但是这样的话只是取出来的数虽然无重复，但是每次取出来的数是有顺序的，可能每次取出的都是第0，1，2个元素 但是有可能第一层循环取出的是0 也可能是1或者2，这样的话，循环的次数就有没必要的增加，实际上是A(3,N)和C(3,N)的区别，于是优化如下。

- (BOOL)seekRandomThreeElementSum:(NSInteger)sum Arr:(NSArray *)array {
    NSInteger b,c,d,i,j,k;
    for (i = 0; i < array.count - 2; i ++) {//因为是三个数 所以第一层循环只用循环数组个数减2的次数
        b = [array[i] integerValue];
        for (j = i + 1 ; j < array.count - 1; j ++) {
            c = [array[j] integerValue];//在i不变的时候 j一直增加 全走一遍
            for (k = j + 1; k < array.count; k ++) {
                d = [array[k] integerValue];//在I,j不变的时候 k一直增加 全走一遍  
                if (b + c + d == sum) {
                    NSLog(@"have the sum");
                    return YES;
                }
            }
        }
    }
    NSLog(@"have not the sum");
    return NO;
}

但是三层for循环时间复杂度还是比较大，从网上找了比较好的优化方法，思路是先将数组排序，外层遍历和上边的方法一样，只遍历count -2次，然后前边的数往后赶，后边的数往前赶，利用双指针遍历，时间复杂度能减少一半，如下：

- (BOOL)seekRandomThreeElementSum1:(NSInteger)sum Arr1:(NSArray *)array {
    NSArray *arr1 = [array sortedArrayUsingComparator:^NSComparisonResult(id  _Nonnull obj1, id  _Nonnull obj2) {
        return [obj1 compare:obj2];
    }];//将数组排序
    NSLog(@"arr == %@",arr1);
    NSInteger length = arr1.count;
    // 三个数 只需循环length - 2次；
    for (NSInteger i = 0; i < length - 2; i ++) {
        NSInteger left = i + 1;
        NSInteger right = length - 1;
        NSInteger m, n, l, all;
        while (left < right) {
            m = [arr1[i] integerValue];
            n = [arr1[left] integerValue];
            l = [arr1[right] integerValue];
            all = m + n + l;
            if (all == sum) {
                NSLog(@"have the sum");
                return YES;
            }
            if (all < sum) {
                left ++;
            }
            if (all > sum) {
                right --;
            }
        }
    }
    NSLog(@"have not the sum");
    return NO;
}

综上第三种方法才是最优解。
大家可以输入测试代码试一下，结果我就不演示了，应该没有错的，测试代码给你们。

    [self seekRandomThreeElementSum1:5 Arr1:@[@(1),@(2),@(4),@(5),@(6),@(7),@(3)]];//没有
    [self seekRandomThreeElementSum1:6 Arr1:@[@(1),@(2),@(3),@(4),@(5),@(6),@(7)]];//有
    [self seekRandomThreeElementSum1:7 Arr1:@[@(1),@(4),@(3),@(5),@(6),@(7)]];//没有
    [self seekRandomThreeElementSum1:8 Arr1:@[@(1),@(4),@(3),@(5),@(6),@(7)]];//有
    [self seekRandomThreeElementSum1:3 Arr1:@[@(1),@(4),@(3),@(5),@(6),@(7)]];//没有