算法题之: 三数求和并去重

题目:对于一个整数的数组, 是否存在a, b, c 使得 a + b + c = 0, 返回a b c 数组

相同数组只返回一个, 例如: [-1, -2, 6, 5, 0, 1, 2, -1, -1] 返回 [[-1, 0, 1], [-2, 0, 2], [-1, -1, 2]]

调用方法

    NSArray*array =@[@-1,@0,@7,@-3,@1,@2,@-2,@2,@-2];

    NSLog(@"测试结果: %@", [self filterArray:array sumTarget:0]);

代码如下:

- (NSMutableArray *)filterArray:(NSArray *)array sumTarget:(NSInteger)sumTarget

{

    NSMutableArray *mutArray = [NSMutableArray array];

    // 数组元素小于2个直接返回

    if(array.count<=2) return mutArray;

    NSMutableArray*sortArray = [NSMutableArray arrayWithArray:array];

    // 将原数组正序排列，这一步很重要，乱序数组很难处理

    [sortArraysortUsingComparator:^NSComparisonResult(id  _Nonnullobj1,id  _Nonnullobj2) {

        return[obj1 compare:obj2];

    }];

    // 循环正序数组

    for(inti =0; i < sortArray.count-1; i ++)

    {

        // 创建最小值下标，最大值下标

        NSIntegr low = i +1;

        NSInteger high = sortArray.count-1;

        // A+B+C=0,  定义-C，为了之后让 A+B=-C

        NSInteger target =sumTarget- [sortArray[I] integerValue];

        if(i >0 && sortArray[i] == sortArray[i -1]) {

            continue;

        }

        // 始终保证 最大值下标 > 最小值下标

        // 思路就是最大值不减小，最小值不短增大，最小值不会超过最大值

        // 直接找到对应值, 相同值去重

        while(low < high) {

            // 创建sum为: 两个数组和，即A+B

            NSIntegersum = [sortArray[low]integerValue] + [sortArray[high]integerValue];

            // 如果A+B==-C,即A+B+C=0

            if(sum == target) {

                [mutArrayaddObject:@[sortArray[low], sortArray[high], sortArray[i]]];

                // 如果当前最小值和下一位相等，下标往后移位，去重

                while(low < high && [sortArray[low]integerValue] == [sortArray[low+1]integerValue]) {

                    low +=1;

                }

                // 如果当前最大值和前一位相等，下标往前移位，去重

                while(low < high && [sortArray[high]integerValue] == [sortArray[high-1]integerValue]) {

                    high -=1;

                }

                // 最小值向后移动一位，最大值向前移动一位

                low +=1;

                high -=1;

            }elseif(sum < target) {

                low +=1;

            }else{

                high -=1;

            }

        }

    }

    returnmutArray;

}