剑指Offer - 九度1352 - 和为S的两个数字

剑指Offer - 九度1352 - 和为S的两个数字
2014-02-05 18:15
题目描述:
输入一个递增排序的数组和一个数字S,在数组中查找两个数,是的他们的和正好是S,如果有多对数字的和等于S,输出两个数的乘积最小的。
输入:
每个测试案例包括两行:
第一行包含一个整数n和k,n表示数组中的元素个数,k表示两数之和。其中1 <= n <= 10^6,k为int
第二行包含n个整数,每个数组均为int类型。
输出:
对应每个测试案例,输出两个数,小的先输出。如果找不到,则输出“-1 -1”
样例输入:
6 15
1 2 4 7 11 15
样例输出:
4 11
题意分析:
  给定一个已排好序的数组,求出是否能找到两个数,使得它们和为S。因为数组已排好序,所以很容易想到二分查找。
  从左往右对于每个a[i],查找a[i + 1]到a[n]中是否存在a[k]=S-a[i]即可。显然时间复杂度是O(n * log(n))。对于10^6的数量级,你也知道一定会超时啦,所以还有更好的方法。
  另一种方法,是在左右两端各方一个指针,看看两者加起来的和sum和S的大小关系,然后把左指针右移,或是右指针左移来进行调整,直到sum等于S。
  如果两指针的位置已经交叉了,说明无解,输出“-1 -1”。
  由于两个指针走到同一处的时候,算法就终止了。因此最坏情况是所有元素被访问一次,时间复杂度为O(n),空间复杂度为O(1)。
剑指Offer - 九度1352 - 和为S的两个数字
 1 // 688158    zhuli19901106    1352    Accepted    点击此处查看所有case的执行结果    4928KB    673B    1420MS
 2 // 201401311706
 3 #include <cstdio>
 4 using namespace std;
 5 
 6 const int MAXN = 1000005;
 7 int a[MAXN];
 8 int n;
 9 int k;
10 
11 int main()
12 {
13     int i;
14     bool suc;
15     int ll, rr;
16     int sum;
17     
18     while (scanf("%d%d", &n, &k) == 2) {
19         for (i = 0; i < n; ++i) {
20             scanf("%d", &a[i]);
21         }
22         suc = false;
23         ll = 0;
24         rr = n - 1;
25         while (ll < rr) {
26             sum = a[ll] + a[rr];
27             if (sum < k) {
28                 ++ll;
29             } else if (sum > k) {
30                 --rr;
31             } else {
32                 suc = true;
33                 break;
34             }
35         }
36         if (suc) {
37             printf("%d %d\n", a[ll], a[rr]);
38         } else {
39             printf("-1 -1\n");
40         }
41     }
42 
43     return 0;
44 }
剑指Offer - 九度1352 - 和为S的两个数字

剑指Offer - 九度1352 - 和为S的两个数字

上一篇:HDU 4815 Little Tiger vs. Deep Monkey 2013 长春现场赛C题


下一篇:剑指Offer - 九度1356 - 孩子们的游戏(圆圈中最后剩下的数)