leetcode之两数之和

前言

本文是leetcode 第一题两数之和c++解法

一、两数之和题目

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

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

示例:
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9，所以返回 [0, 1]

二、解题

1.c++暴力法解决

代码如下：

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

};

int main() {
	vector<int> twoSum = { 2, 7, 11, 15 };
	int n = 9;
	vector <int>  k;
	Solution x;
	k = x.twoSum(twoSum, n);
	for (int i = 0; i <= 1; i++)
	{
		cout << k[i];
	}
	return 0;
}

注意这里的解题过程是在编译器中的运行代码，来leetcode上提交只需要提交solution类即可。

注：vector是c++容器，某种意义上可以当作数组来用

2.两遍哈希表

代码如下：

#include<iostream>
#include<vector>
#include<map>
using namespace std;
class Solution {
public:
	vector<int> twoSum(vector<int>& nums, int target) {
		map<int,int> a;
		int r1, r2;
		for (int i = 0; i < nums.size(); i++)
			a.insert(map<int, int>::value_type(nums[i], i));
		for (int i = 0; i < nums.size(); i++)
		{
			if (a.count(target - nums[i]) > 0 && (a[target - nums[i]] != i))
			{//count函数是判断该数是否在这个哈希表中，若在，返回值大于0
				r1 = i;
				r2 = a[target - nums[i]];
				break;
			}
		}
		return { r1,r2 };
	}

};

int main() {
	vector<int> twoSum = { 2, 7, 11, 15 };
	int n = 9;
	vector <int>  k;
	Solution x;
	k = x.twoSum(twoSum, n);
	for (int i = 0; i <= 1; i++)
	{
		cout << k[i];
	}
	return 0;
}

1.map是STL的一个关联容器，它提供一对一的hash。具体用法，可以看看这https://blog.csdn.net/sevenjoin/article/details/81943864
2.文中有关迭代器的知识自寻

3.一遍哈希表

代码如下：

#include<iostream>
#include<vector>
#include<map>
using namespace std;
class Solution {
public:
	vector<int> twoSum(vector<int>& nums, int target) {
		map<int,int> a;
		int r1, r2;

		for (int i = 0; i < nums.size(); i++)
		{
			if (a.count(target - nums[i]) > 0 && (a[target - nums[i]] != i))
			{//count函数是判断该数是否在这个哈希表中，若在，返回值大于0
				r1 = a[target - nums[i]];
				r2 = i;
				break;
			}
			a[nums[i]] = i;
		}
		return { r1,r2 };
	}

};

int main() {
	vector<int> twoSum = { 2, 7, 11, 15 };
	int n = 9;
	vector <int>  k;
	Solution x;
	k = x.twoSum(twoSum, n);
	for (int i = 0; i <= 1; i++)
	{
		cout << k[i];
	}
	return 0;
}

该方法在使用迭代方法，在两遍哈希表的基础上再次优化

总结

这道题学习算法还在其次，主要是学会了如何使用leetcode，并成功提交了第一题，记录一下进步。