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個(gè)數(shù)組和1個(gè)數(shù)，在數(shù)組中找到兩個(gè)數(shù)，它們的和等于給定數(shù)，返回這兩個(gè)數(shù)在數(shù)組中的索引。
兩重循環(huán)最簡(jiǎn)單，但肯定超時(shí)。數(shù)組排序是必須的，這樣可以有1定的次序來(lái)求和。但如果順序查找，就又是兩重循環(huán)了。
所以，可以以這樣的次序查找：從兩頭，到中間。保存兩個(gè)指針，左側(cè)1個(gè)，右側(cè)1個(gè)，兩個(gè)指針指向的數(shù)相加，會(huì)有以下結(jié)果和操作：
注：參數(shù)是援用，排序時(shí)要使用拷貝的數(shù)組
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
// 復(fù)制數(shù)組，由于要排序
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) { // 數(shù)小了，left右移
left++;
} else if(sum > target) { // 數(shù)大了，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網(wǎng)，php教程，php學(xué)習(xí)，php手冊(cè)，CMS模版制作
聲明：本站大部分內(nèi)容是作者原創(chuàng)，少部分收集于互聯(lián)網(wǎng)供大家一起學(xué)習(xí)，原版權(quán)很多不明，如有侵權(quán)請(qǐng)聯(lián)系本站，謝謝！
粵ICP備14040726號(hào)-1?? 2015-2020 程序員人生 版權(quán)所有
