1.题目
Given an array of integers, find two numbers such that they add up to a specific target number.
The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.
You may assume that each input would have exactly one solution.
Input: numbers={2, 7, 11, 15}, target=9
Output: index1=1, index2=2
2.解决方案之1
typedef struct node{
int originalIndex;
int val;
node(){};
node(int index, int v):originalIndex(index),val(v){}
} Node;
bool compare(const Node& a, const Node& b){
return a.val < b.val;
}
class Solution {
public:
vector<int> twoSum(vector<int> &numbers, int target) {
vector<int> result;
int length = numbers.size();
vector<Node> nums(length);
for(int i = 0; i < numbers.size(); ++i){
nums[i] = Node(i, numbers[i]);
}
sort(nums.begin(), nums.end(), compare);
int left = 0;
int right = length - 1;
while(left < right){
int sum = nums[left].val + nums[right].val;
if(sum == target){
result.push_back(min(nums[left].originalIndex + 1, nums[right].originalIndex + 1));
result.push_back(max(nums[left].originalIndex + 1, nums[right].originalIndex + 1));
break;
}else if(sum < target){
left++;
}else{
right--;
}
}
return result;
}
};
思路：先排序，然后头尾相加进行判断，如果太小了，把左侧的标记index往右移动1个，如果太大了，把右侧的标记index往左移动，直到找到为止。
http://www.waitingfy.com/archives/1577