剑指Offer：和为 S 的两个数字 VS 和为 S 的连续正数序列

输入一个递增排序的数组和一个数字S，在数组中查找两个数，使得他们的和正好是S，如果有多对数字的和等于S，输出两个数的乘积最小的。

vector<int> FindNumbersWithSum(const vector<int>& Array, const int& sum) { vector<int> result; if(Array.size() < 2 || sum < Array[0] + Array[1]) return result; vector<int>::size_type left = 0, right = Array.size() - 1; int v1 = Array[left], v2 = Array[right], product = 0x7fffffff;// product 记录乘积，初始化为 int 最大值 while(left < right) { int curSum = Array[left] + Array[right]; if(sum == curSum) { int productLeftRight = Array[left] * Array[right]; if(productLeftRight < product) { product = productLeftRight; v1 = Array[left]; v2 = Array[right]; } left++; } else if(curSum < sum) left++; else right--; } if(0x7fffffff != product) { result.push_back(v1); result.push_back(v2); } return result; } 和为S的连续正数序列

vector<vector<int> > FindContinuousSequence(const int& sum) {/ vector<vector<int> > vecResult; if(sum < 3) return vecResult; int left = 1, right = 2, curSum = 3, mid = (sum + 1) / 2;// left 增长到 mid-1 就停止，因为 mid+mid+1 大于 sum while(left < mid) { if(sum == curSum) { vector<int> result(right-left+1); vector<int>::size_type i = 0; for(int value=left; value <= right; value++) result[i++] = value; vecResult.push_back(result); curSum -= left; left++; } else if(curSum > sum) { curSum -= left; left++; } else { right++; curSum += right; } } return vecResult; }