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;
}
};