题:找出有序数组中和等于指定数的两个数

分析:

数组是有序的;数组中可能存在两个数相加的和等于给定的值,找出这两个数,如果没有提示。

思路:

首先想到的必须遍历数组,这点是毋庸置疑的。这时需要考虑的就是怎样遍历数组以及时间复杂度问题。

方案:

1、双重遍历

最简单也是最笨重的想法是双重遍历:将每个数与另外的数相加,判断是否等于目标值,时间复杂度为O(n*n)。

2、快速查找法

方法一:从两端开始,分别向中间取值匹配。时间复杂度为O(n)。

(1)如果两数之和>目标值,说明较大加数需要小些,向数组的较小值方向移位取值继续和原较小值重新匹配。

(2)如果两数之和<目标值,说明较小加数需要大些,向数组的较大值方向移位取值继续和原较大值重新匹配。

方法二:近一步思考:以数组中间下标(index)为分界点,分别向左右两边取值匹配。时间复杂度为O(n)。

(1)若两数之和>目标值,说明较小加数还要再小,向数组的较小值方向移位取值与原较大值重新匹配。

(2)若两数之和<目标值,说明较大加数还要再大,向数组的较大值方向移位取值与原较小值重新匹配。

方法三:换一种方式思考, 两个加数一定满足条件:较小加数小于等于目标值的一半,并且较大值大于等于目标值的一半(较小加数<= (目标值/2) <= 较大加数);那么只需要找出该数组的较小加数和较大加数分界index,以该分界为起点分别往左右两边逐个取值匹配。比较的方式遵循方法二的(1)(2)。时间复杂度仍为O(n)。

代码实践

双重遍历
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
NSInteger targetNumber = 90;
NSArray *arr = @[@"4",@"8",@"10",@"15",@"20",@"30",@"35",@"49",@"51",@"60",@"60",@"63",@"70",@"89"];
BOOL result = NO;

for(NSInteger i = 0 ; i< arr.count; i++){
NSInteger minNumber = [arr[i] integerValue];

for (NSInteger j = i+1;j< arr.count;j++) {
NSInteger maxNumber = [arr[j] integerValue];
if(minNumber + maxNumber == targetNumber ){
NSLog(@"search3 :::::::%li---%li",minNumber,maxNumber);
result = YES;
break;
}
}
}

if(result == NO){
NSLog(@"未找到");
}
快速查找

方法一:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
NSInteger targetNumber = 90;
NSArray *arr = @[@"4",@"8",@"10",@"15",@"20",@"24",@"30",@"35",@"49",@"50",@"60",@"63",@"70",@"89"];
BOOL result = NO;
NSInteger minIndex = 0 ;
NSInteger maxIndex = arr.count-1;
do {
NSInteger sumNumber = [arr[minIndex] integerValue]+ [arr[maxIndex] integerValue];
if(sumNumber > targetNumber){
maxIndex -- ;
}else if(sumNumber < targetNumber){
minIndex++;
}else{
NSLog(@"%@---%@",arr[minIndex],arr[maxIndex]);
minIndex++;
maxIndex--;
result = YES;
}

} while (minIndex <= maxIndex);

if(result == NO){
NSLog(@"未找到");
}

方法二:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
NSInteger targetNumber = 90;
NSArray *arr = @[@"4",@"8",@"10",@"15",@"20",@"24",@"30",@"35",@"49",@"50",@"60",@"63",@"70",@"89"];
NSInteger midIndex = arr.count*0.5;
BOOL result = NO;
if(midIndex > 0){
NSInteger minIndex = midIndex ;
NSInteger maxIndex = midIndex+1;
do {
NSInteger sumNumber = [arr[minIndex] integerValue]+ [arr[maxIndex] integerValue];
if(sumNumber > targetNumber){
minIndex -- ;
}else if(sumNumber < targetNumber){
maxIndex++;
}else{
NSLog(@"%@---%@",arr[minIndex],arr[maxIndex]);
minIndex--;
maxIndex++;
result = YES;
}

} while (minIndex >= 0 && maxIndex < arr.count);
}

if(result == NO){
NSLog(@"未找到");
}

方法三:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
NSInteger targetNumber = 90;
NSArray *arr = @[@"4",@"8",@"10",@"15",@"20",@"30",@"35",@"49",@"51",@"60",@"60",@"63",@"70",@"89"];
NSInteger midIndex = 0;
BOOL result = NO;
for (NSInteger i = 0;i<arr.count;i++) {
if([arr[i] integerValue] > targetNumber*0.5){
midIndex = i - 1;
NSLog(@"%ld",midIndex);
break;
}

}

if(midIndex != -1){
NSInteger minIndex = midIndex;
NSInteger maxIndex = midIndex + 1;
do {
NSInteger sumNumber = [arr[minIndex] integerValue]+ [arr[maxIndex] integerValue];
if (sumNumber > targetNumber) {
minIndex--;
}else if(sumNumber < targetNumber){
maxIndex++;
}else {
NSLog(@"%@---%@",arr[minIndex],arr[maxIndex]);
minIndex--;
maxIndex++;
result = YES;
}
} while (minIndex >= 0 && (maxIndex <= arr.count-1));
}

if(result == NO){
NSLog(@"未找到");
}