// 面试题57(一):和为s的两个数字 // 题目:输入一个递增排序的数组和一个数字s,在数组中查找两个数,使得它们 // 的和正好是s。如果有多对数字的和等于s,输出任意一对即可。 #include <cstdio> bool FindNumbersWithSum(int data[], int length, int sum, int* num1, int* num2) { bool found = false; if (length < 1 || num1 == nullptr || num2 == nullptr) return found; int ahead = 0; int behind = length - 1; while (ahead <= behind) { long long result = data[ahead] + data[behind]; if (result == sum) { *num1 = data[ahead]; *num2 = data[behind]; found = true; break; } else if (result > sum) --behind; else ++ahead; } return found; }
// ====================测试代码==================== void Test(const char* testName, int data[], int length, int sum, bool expectedReturn) { if (testName != nullptr) printf("%s begins: ", testName); int num1, num2; int result = FindNumbersWithSum(data, length, sum, &num1, &num2); if (result == expectedReturn) { if (result) { if (num1 + num2 == sum) printf("Passed. \n"); else printf("FAILED. \n"); } else printf("Passed. \n"); } else printf("FAILED. \n"); } // 存在和为s的两个数字,这两个数字位于数组的中间 void Test1() { int data[] = { 1, 2, 4, 7, 11, 15 }; Test("Test1", data, sizeof(data) / sizeof(int), 15, true); } // 存在和为s的两个数字,这两个数字位于数组的两段 void Test2() { int data[] = { 1, 2, 4, 7, 11, 16 }; Test("Test2", data, sizeof(data) / sizeof(int), 17, true); } // 不存在和为s的两个数字 void Test3() { int data[] = { 1, 2, 4, 7, 11, 16 }; Test("Test3", data, sizeof(data) / sizeof(int), 10, false); } // 鲁棒性测试 void Test4() { Test("Test4", nullptr, 0, 0, false); } int main(int argc, char* argv[]) { Test1(); Test2(); Test3(); Test4(); return 0; }测试代码
分析:书中ahead和behind写反了。
碰到的第一组数,即最外圈差值最大的两个数字,必定是乘积最小。
class Solution { public: vector<int> FindNumbersWithSum(vector<int> array,int sum) { int length = array.size(); int ahead = 0; int behind = length - 1; vector<int> num; while (ahead < behind) { int curSum = array[ahead] + array[behind]; if (curSum == sum) { num.push_back(array[ahead]); num.push_back(array[behind]); break; } else if (curSum > sum) --behind; else ++ahead; } return num; } };牛客网提交代码