题：找出有序数组中和等于指定数的两个数
分析：
数组是有序的；数组中可能存在两个数相加的和等于给定的值，找出这两个数，如果没有提示。
思路：
首先想到的必须遍历数组，这点是毋庸置疑的。这时需要考虑的就是怎样遍历数组以及时间复杂度问题。
方案：
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(@"未找到");
}
|
