剑指OFFER-和为S的两个数字

QuestionSolution双指针

Question

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

输出描述: 对应每个测试案例，输出两个数，小的先输出。

关键词：有序求和 双指针

Solution

虽然可以暴力循环，但是上一题用双指针找连续和，注意指针是从头尾开始就行了。

双指针

时间复杂度：O() 空间复杂度：O()

Python class Solution: def FindNumbersWithSum(self, array, tsum): p1, p2 = 0, len(array)-1 ans = [] while p1<p2: temp = array[p1] + array[p2] if temp == tsum: return [array[p1], array[p2]] elif temp<tsum: p1 += 1 else: p2 -= 1 return ans C++ class Solution { public: vector<int> FindNumbersWithSum(vector<int> array,int sum) { vector<int> ans={}; int p1 = 0, p2 = array.size()-1; while(p1 < p2){ int temp = array[p1] + array[p2]; if (temp == sum){ ans = {array[p1], array[p2]}; return ans; } if(temp < sum) p1++; else p2--; } return ans; } };