Leetcode 热题1. 两数之和 (C++，暴力，map完整版代码)

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 的那 两个 整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。

你可以按任意顺序返回答案。

示例 1：

输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
示例 2：

输入：nums = [3,2,4], target = 6
输出：[1,2]
示例 3：

输入：nums = [3,3], target = 6
输出：[0,1]

方法一：暴力求解

#include <iostream>
#include <vector>
using namespace std;

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
	for (int i = 0 ; i < nums.size() - 1; ++i){
		for (int j = i+1; j < nums.size(); ++j){ 
			if(nums[i] + nums[j] == target)
			return {i,j};
		}	
	}
	return {};
    }
};

int main(){
	Solution solution;
	vector<int> position;
	vector<int> arr = {1,2,3,4,5,6,7,8,9};
	int target = 5;
	position = solution.twoSum(arr,target);
	for(auto i : position)
		cout << i << endl;
	return 0 ;
}

方法二：map

#include <iostream>
#include <vector>
#include <map>
using namespace std;

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

int main(){
	Solution solution;
	vector<int> position;
	vector<int> arr = {1,2,3,4,5,6,7,8,9};
	int target = 7;
	position = solution.twoSum(arr,target);
	for(auto i : position)
		cout << i << endl;
	return 0 ;
}