Given an array of integers, return indices of the two numbers such that they add up to a specific target.
You may assume that each input would have exactly one solution.
Example:
Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].
給定1個數組和1個數，在數組中找到兩個數，它們的和等于給定數，返回這兩個數在數組中的索引。
兩重循環最簡單，但肯定超時。數組排序是必須的，這樣可以有1定的次序來求和。但如果順序查找，就又是兩重循環了。
所以，可以以這樣的次序查找：從兩頭，到中間。保存兩個指針，左側1個，右側1個，兩個指針指向的數相加，會有以下結果和操作：
注：參數是援用，排序時要使用拷貝的數組
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
// 復制數組，由于要排序
vector<int> cp(nums);
// 先排序
sort(cp.begin(), cp.end());
int right = cp.size()-1;
int left = 0;
while(right > left) {
int sum = cp[right] + cp[left];
if(sum == target) {
break;
} else if(sum < target) { // 數小了，left右移
left++;
} else if(sum > target) { // 數大了，right左移
right--;
}
}
vector<int> r;
int a=-1,b=-1;
// 取出索引
for(int i=0;i<nums.size();i++) {
if(nums[i] == cp[left]&&a==-1) a = i;
else if(nums[i] == cp[right]&&b==-1) b = i;
}
if(a>b) {
int t = a;
a=b,b=t;
}
r.push_back(a);
r.push_back(b);
return r;
}
};
程序員人生，我編程，我富裕，記住wfuyu網，php教程，php學習，php手冊，CMS模版制作
聲明：本站大部分內容是作者原創，少部分收集于互聯網供大家一起學習，原版權很多不明，如有侵權請聯系本站，謝謝！
粵ICP備14040726號-1?? 2015-2020 程序員人生 版權所有
