[数据结构与算法]leetcode_1_TwoSum

2021.10.22开始每天坚持刷刷leetcode，深知自己的基础太薄弱，刷题的同时去弥补其他不会的知识点，使得自己能够更深刻地理解并运用，希望自己能够坚持下去！先从简单的开始，网站是leetcode，借鉴的书籍《Leetcode 刷题题解答案》，有需要的小伙伴评论区留言，后期如果刷到有相似的会总结在一个章节，如果有什么错误的话，希望大家批评指正！

1. TwoSum

题目名称： 1、两数之和
题目介绍： 给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出和为目标值 target的那两个整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案。

示例1：

输入：nums = [2, 6, 3, 8], targe = 11
输出：[2, 3]

思路解析：
1、采用最简单直接的方法，遍历两次数组，找到能满足条件的数值，大致形式如下：

vector<int> result;
for (int i = 0; i < nums.size(); ++i) {
	for (int j = i+1; j < nums.size(); ++j) {
		if (nums[i] + num[j] == targe) {
			result.push_back(i);
			result.push_back(j);
			break;
		}
	}
}	 

以上代码的时间复杂度为O(n²)，系统会判定超时；
2、如果我们先把nums排好序，再利用左右夹逼寻找满足条件的数值，那样会怎么样？试验证明，虽然时间复杂度减少了，但是返回的序列号（下标）是排好序之后的序列号（下标），这个方法目前不可行，但实施起来可能有些麻烦，对着得到的下标寻找排好序之前的下标。
3、hash。利用一个哈希表（散列），存储每个数值对应的下标。

class Solution {
public: 
	vector<int> twoSum(vector<int>& nums, int targe) {
		vector<int> result;  //return type
		unordered_map<int, int> mapping;  //hash
		//build connection
		for (int i = 0; i < nums.size(); ++i) 
			mapping[num[i]] = i;
		for (int i = 0; i < nums.size(); ++i) {
			int other = targe - nums[i];
			
			//1.mapping.find(other) != mapping.end();
			//2.mapping[other] > i
			if ((mapping.find(other) != mapping.end()) && (mapping[other] > i)) {
				result.push_back(i);
				result.push_back(mapping[other]);
				break;
			}
		}	
		return result;
	}
};

以上便是利用hash实现的代码，时间复杂度为O(n);
一边借鉴着一边理解，如果想了解更多散列表的知识，请点击以下链接。
数据结构之Hash