LeetCode Two Sum
來源：程序員人生 發布時間：2015-03-31 08:15:40 閱讀次數：3299次
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
生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
