给定已排序数组,找出和为特定数值的两个数

给定已排序数组,找出和为特定数值的两个数。假定数组中的数值都不相同。

方法一:穷举法

1
2
3
4
5
6
7
8
9
10
11
12
13
- (void)fineTwoNumberWithArray0:(int *)nums count:(int)count target:(int)target {
int leftNum,rightNum;
for (int i = 0; i < count - 1; i++) {
leftNum = nums[i];
for (int j = i + 1; j < count; j++) {
rightNum = nums[j];
if ((rightNum + leftNum) == target) {
NSLog(@"%d + %d = %d",leftNum, rightNum, target);
}
}
}
}

T(n) = (n - 1 + 1) * n / 2 = (n^2) / 2 = O(n^2),即时间复杂度:O(n^2)。

方法二

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
- (void)fineTwoNumberWithArray1:(int *)nums count:(int)count target:(int)target {
int left = 0;
int right = count - 1;
int sum = 0;
while(left <= right) {
sum = nums[left] + nums[right];
if (sum < target) {
left += 1;
} else if (sum > target) {
right -= 1;
} else {
NSLog(@"%d + %d = %d",nums[left], nums[right], target);
left += 1;
right -= 1;
}
}
}

T(n) <= n - 1 = O(n) 时间复杂度:O(n)。