题目:对于一个整数的数组, 是否存在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;
}
网友评论