Two Sum II – Input array is sorted
Question:
Similar to Question [1. Two Sum], except that the input array is already sorted in
ascending order.
同上题：先排序，然后从开头和结尾同时向中间查找，原理也比较简单。O(nlogn) runtime, O(1) space
vector<int> twoSumSored(vector<int>& nums, int target){
vector<int> vecCopy(nums);
int i=0,n=2,l=0,r = nums.size()-1;
sort(vecCopy.begin(),vecCopy.end());
int j=nums.size()-1;
while(i<j)
{
int sum = nums[i]+nums[j];
if (sum <target)
{
i++;
}
else if (sum > target)
{
j--;
}
else
{
vector<int> index;
index.push_back(i+1);
index.push_back(j+1);
return index;
}
}
}