题意
给定一个数字序列和一个目标值target，返回二个数的和等于target的下标。? 167代码在最后。
题解
1、暴力法
? ? ? ? 直接进行双重遍历，查找到目标值下标。
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
for(int i=0; i<nums.size(); i++){
for(int j=i+1; j<nums.size(); j++){
if(nums[j] + nums[i] == target){
return {i,j};
}
}
}
return {};
}
}2、采用hash_map 的方法
如果temp中没有发现target-nums[i]的值，那么将这个值和下标存入。
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
map<int, int> temp;
// vector<int> res;
for(int i=0; i<nums.size(); i++){
int number=target-nums[i];
if(temp.find(number)!=temp.end()){
return{temp[number], i};
}
temp[nums[i]] = i;
}
return {};
}
}3、双指针??167. Two Sum II
先排序然后采用双指针，相向而行（两个指针从两边出发一起向中间移动直到两个指针相遇）这个解题方法和167的two sumII 的方法一致。
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
vector<int> number = nums;
sort(nums.begin(), nums.end());
int start=0, end=nums.size()-1;
vector<int> res;
while(start<end){
int sum = nums[start]+nums[end];
// cout<<sum<<endl;
if( sum==target){
res.push_back(nums[start]);
res.push_back(nums[end]);
break;
}
else if(sum<target) start++;
else end--;
}
vector<int> index;
if(res.size()==0) return {};
else{
int in=0;
for(int i=0; i<number.size(); i++){
if(number[i]==res[0] || number[i]==res[1]) index.push_back(i);
}
}
return index;
}
};167?
class Solution {
public:
vector<int> twoSum(vector<int>& numbers, int target) {
int start=0, end=numbers.size()-1;
while(start<end){
int temp = numbers[start] + numbers[end];
if(temp==target) return {start+1,end+1};
else if(temp > target) end--;
else start++;
}
return {};
}
};
