前言

一日不學習，恐落后于世界久矣。

最近有朋友面試，面試一些簡單的算法，多了不說，總結(jié)如下。

1、判斷整數(shù)數(shù)組中有沒有隨機三個數(shù)之和等于一個已知數(shù)

看到這個題目，我簡單粗暴的想起了三層for循環(huán)，需要考慮的是三層for循環(huán)里的數(shù)，每層的數(shù)都不能是一樣的，于是寫出了這樣的方法。

- (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) {//保證外層循環(huán)的數(shù)和本層循環(huán)不一樣
                c = [array[j] integerValue];
                for (k = 0; k < array.count; k ++) {
                    if (k != i && k != j) {//保證外層循環(huán)的數(shù)和本層循環(huán)不一樣
                        d = [array[k] integerValue];
                        if (b + c + d == sum) {
                            NSLog(@"have the sum");
                            return YES;
                        }
                    }
                }
            }
        }
    }
    NSLog(@"have not the sum");
    return NO;
}

但是這樣的話只是取出來的數(shù)雖然無重復，但是每次取出來的數(shù)是有順序的，可能每次取出的都是第0，1，2個元素 但是有可能第一層循環(huán)取出的是0 也可能是1或者2，這樣的話，循環(huán)的次數(shù)就有沒必要的增加，實際上是A(3,N)和C(3,N)的區(qū)別，于是優(yōu)化如下。

- (BOOL)seekRandomThreeElementSum:(NSInteger)sum Arr:(NSArray *)array {
    NSInteger b,c,d,i,j,k;
    for (i = 0; i < array.count - 2; i ++) {//因為是三個數(shù) 所以第一層循環(huán)只用循環(huán)數(shù)組個數(shù)減2的次數(shù)
        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循環(huán)時間復雜度還是比較大，從網(wǎng)上找了比較好的優(yōu)化方法，思路是先將數(shù)組排序，外層遍歷和上邊的方法一樣，只遍歷count -2次，然后前邊的數(shù)往后趕，后邊的數(shù)往前趕，利用雙指針遍歷，時間復雜度能減少一半，如下：

- (BOOL)seekRandomThreeElementSum1:(NSInteger)sum Arr1:(NSArray *)array {
    NSArray *arr1 = [array sortedArrayUsingComparator:^NSComparisonResult(id  _Nonnull obj1, id  _Nonnull obj2) {
        return [obj1 compare:obj2];
    }];//將數(shù)組排序
    NSLog(@"arr == %@",arr1);
    NSInteger length = arr1.count;
    // 三個數(shù) 只需循環(huán)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;
}

綜上第三種方法才是最優(yōu)解。
大家可以輸入測試代碼試一下，結(jié)果我就不演示了，應該沒有錯的，測試代碼給你們。

    [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)]];//沒有