首页 > 代码库 > IT公司100题-14-排序数组中和为给定值的两个数字

IT公司100题-14-排序数组中和为给定值的两个数字

2024-07-16 19:43:25   221人阅读

问题描述：

输入一个升序排序的数组，给定一个目标值target，求数组的两个数a和b，a+b=target。如果有多个组合满足这个条件，输出任意一对即可。
例如，输入升序数组【1, 3, 4, 5, 13, 17】和目标值20。输出3和17。
分析：
最简单的办法，直接遍历，时间复杂度为O(n^2)。
双下标法：low和high
a[low]+a[high] < target, low++;
a[low]+a[high] > target, high–;
a[low]+a[high] == target, return low and high;
 
代码实现如下所示：
 1 // 14.cc 2 #include 3 using namespace std; 4  5 bool find_two(int* a, size_t size, int target, int& t1, int& t2) { 6     bool flag = false; 7     if (size < 2) 8         return flag; 9 10     size_t low = 0;11     size_t high = size - 1;12 13     while (low < high) {         int s = a[low] + a[high];         if (s > target)14             high--;15         else if (s < target)16             low++;17         else {18             t1 = a[low];19             t2 = a[high];20             flag = true;21             return flag;22         }23     }24     return flag;25 }26 27 int main() {28     int a[] = {1, 3, 4, 5, 13, 17};29     int size = sizeof(a) / sizeof(int);30     int target = 20;31     int t1, t2;32     bool flag = find_two(a, size, target, t1, t2);33     if (flag)34         cout << t1 << " + " << t2 << " = " << target << endl;35     else36         cout << "can not find t1 and t2." << endl;37     return 0;38 }

 


联系
我们