题目描述

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

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

示例:

给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

算法1

首先想到的是暴力法，给出一个数组 找到和为某个数的情况，根据排列组合，有n^2那么多的情况，我们通过ij两重循环遍历所有情况来求得结果,ij就是所求得的结果

算法2

在暴力法中我们发现，算法耗时的地方在于假设其中一个i的情况下如何找到合适的j，合理的数据结构可以提高查找的效率，我们知道哈系表的查找效率是O(1),平衡树的查找效率是o(logn ),因此我们可以建立一个哈系表来加速搜索效率

代码

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

    }
};