算法 1. 两数之和

LeetCode https://leetcode.cn/problems/two-sum/

题目描述

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

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

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

思路

将数组转换为map, key为数组中的元素, value为这个元素在数组中的下标

遍历map, 检查target 与 key的差是否在map中

代码

class Solution {
public:
	vector<int> twoSum(vector<int>& nums, int target) {
		// std:map 内部实现使用红黑树实现的, 是有序的
		// std:unordered_map 内部实现使用哈希表, 数据是无序的, 而且数据也不一定使用的是连续内存
		// 对内存使用有严格要求, 不能接受存储hash table的额外内存开销的情况下使用map
		// 元素要求按顺序存储, 或者常常需要关联访问一个元素的上一个/下一个元素, 或者需要遍历操作的情况下使用map
		// std:unordered_map 通过hash函数计算元素位置, 其查询时间复杂度平均O(1), 最坏O(N)
		// std:map 查询时间复杂度平均O(logN)
		std:unordered_map <int, int> map;
		int size = (int)nums.size();
		for (int i = 0; i < size; ++i) {
			auto iter = map.find(target - nums[i]);
			if (iter != map.end()) {
				return {iter->second, i};
			}
			map[nums[i]] = i;
		}
		return {};
	}
};