LeetCode_1.两数之和-二、方法

时间:2024-04-01 12:35:18

1.方法1(暴力枚举法)

利用两个for循环,对数组进行逐一的遍历,直到找到两个数的和为目标值时返回这两个数的下标。以下为c++实现的完整代码。

# include<iostream>
using namespace std;
#include<vector>
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[i]+nums[j]==target){
					return {i,j};
				}
			}
		}
		return {};
	}	
};
int main(){
	vector<int> num= {3,3};
	int target=6;
	Solution s; 
	vector<int> ans=s.twoSum(num,target);
	for(int i=0;i<ans.size();i++){
		cout<<ans[i]<<" ";
	}
	cout<<endl;
	
	return 0;
}

2.方法2(哈希表法)

边遍历边查找,for循环遍历数组,在遍历过程中,如果能找到(target-nums[i])的值,表明查找成功,直接返回哈希表的值(第一个为nums[i],第二个为i)。如果没找到,则将目前遍历的值与该值的下标放入到哈希表。c++实现代码如下:

#include<iostream>
using namespace std;
#include<vector>
#include<algorithm>
#include<unordered_map>
//哈希方法 

class Solution{
public: 
	vector<int>twoSum(vector<int>& nums,int target){
		unordered_map<int ,int> mp;
		for(int i=0;i<nums.size();i++){
			auto iter=mp.find(target-nums[i]);
			if(iter!=mp.end()){
				return {iter->second,i};
			}
			mp.insert({nums[i],i});
		}
		return {};						
	} 
	
};


int main(){
	vector<int>nums={3,3};
	int target=6;
	Solution s;
	vector<int> ans=s.twoSum(nums,target);
	for(int i=0;i<ans.size();i++){
		cout<<ans[i]<<" ";
	}
	cout<<endl;
	return 0;
}

相关文章