
给定已排序数组,找出和为特定数值的两个数。假定数组中的数值都不相同。
方法一:穷举法
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)。
近期评论