滴水逆向联盟

标题: 基于visual Studio2013解决面试题之0303数组求和 [打印本页]

---

作者: 大灰狼    时间: 2014-7-31 08:32
标题: 基于visual Studio2013解决面试题之0303数组求和

题目





解决代码及点评[cpp] view plaincopy

• <pre code_snippet_id="110707" snippet_file_name="blog_20131213_1_5046989" class="cpp" name="code"><pre code_snippet_id="110707" snippet_file_name="blog_20131213_1_5046989" class="cpp" name="code"><pre code_snippet_id="110707" snippet_file_name="blog_20131213_1_5046989" class="cpp" name="code"><pre code_snippet_id="110707" snippet_file_name="blog_20131213_1_5046989" name="code" class="cpp"><pre code_snippet_id="110707" snippet_file_name="blog_20131213_1_5046989" name="code" class="cpp"></pre><pre code_snippet_id="110707" snippet_file_name="blog_20131213_2_2778714" name="code" class="cpp">/*
•     输入一个已经按升序排序过的数组和一个数字，
•     在数组中查找两个数，使得它们的和正好是输入的那个数字。
•     要求时间复杂度是 O(n)。如果有多对数字的和等于输入的数字，输出任意一对即可。
• */  
•   
• #include <iostream>  
• using namespace std;  
•   
• // 查找函数，pnArr是有序数组  
• // nLen是数组长度  
• // nSum是期望的和  
• // a,b是查找结果下标，如果返回true，那么a,b有效  
• // 如果返回false说明没有办法求和，a,b无效  
• bool Find(int *pnArr, int nLen, int nSum, int &a, int &b)  
• {  
•     int i = 0;  
•     int j = nLen - 1;  
•     // 从两边逼近，i从数组小的一边，j从数组大的一边，逼近期望和  
•     while (i < j)  
•     {  
•         if (pnArr + pnArr[j] > nSum)  // 如果和太大，则减小j，让下次和变小  
•         {  
•             j--;  
•         }  
•         else if (pnArr + pnArr[j] < nSum) // 如果和太小，则增加i，让下次和变大  
•         {  
•             i++;  
•         }  
•         else   // 如果和正好等于期望和，那么说明已经找到了  
•         {  
•             a = i;  
•             b = j;  
•             return true;  
•         }  
•     }  
•   
•     return false;  
• }  
•   
• // 测试主函数  
• int main()  
• {  
•     int nArr[] = {1,3,5,7,9,12,32,45,56,78,90};  
•     int nLen = sizeof(nArr) / sizeof(int);  
•     int i, j;  
•     int nSum;  
•     cout<<"请输入一个数字:";  
•     cin>>nSum;  
•     if (Find(nArr, nLen, nSum, i, j))  
•     {  
•         cout<<nArr<<" + "<<nArr[j]<<" = "<<nSum<<endl;  
•     }  
•     else  
•     {  
•         cout<<"没有两数之和为"<<nSum<<endl;  
•     }  
•     system("pause");  
•     return 0;  
• }</pre><br><br></pre><br></pre></pre></pre>  
  

代码下载及其运行

代码下载地址：http://download.csdn.net/detail/yincheng01/6704519

解压密码：c.itcast.cn

下载代码并解压后，用VC2013打开interview.sln，并设置对应的启动项目后，点击运行即可，具体步骤如下：

1）设置启动项目：右键点击解决方案，在弹出菜单中选择“设置启动项目”

2）在下拉框中选择相应项目，项目名和博客编号一致

3）点击“本地Windows调试器”运行

程序运行结果

---

欢迎光临 滴水逆向联盟 (http://dtdebug.com/)

Powered by Discuz! X3.2