题目

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 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]

提示：

• 2 <= nums.length <= 104
• -109 <= nums[i] <= 109
• -109 <= target <= 109
• 只会存在一个有效答案

进阶：你可以想出一个时间复杂度小于 O(n2) 的算法吗？

题解

暴力解

用两个for循环来依次查找，如果num[i]+num[j]=target，则两个元素装入vector中，返回vector。

时间复杂度为O(n²)

空间复杂度O(1)

vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> temp;
        for(int i=0;i<nums.size();i++){
            for(int j=i+1;j<nums.size();j++){
                if(nums[i]+nums[j]==target){
                    cout<<"["<<i<<","<<j<<"]"<<endl;
                    temp.push_back(i);
                    temp.push_back(j);
                    return temp;
                }
            }
        }
        return temp;
    }

哈希表

这里我们可以创建一个哈希表,哈希表的格式为(元素，元素索引)。因为我们最后返回的vector存放的是数组索引。for循环依次遍历数组元素，这时我们要想，我们当前要找的元素是什么。假设当前元素为x，我们要满足x+y=target。则我们需要找到y=target-x。若当前y在哈希表中没有找到，则把（当前遍历元素,索引)放入哈希表中，继续遍历元素。

时间复杂度O(nlogn)

空间复杂度O(n)

这里空间复杂度为O(n)比较好理解，因为中间过程使用空间最多为创建的map,其他可以忽略不计。

时间复杂度需要解释一下，在map.insert()这个操作中时间复杂度为O(logn)，因为multimap底层是用红黑树实现的，红黑树是一种自平衡二叉搜索树。那么往平衡树中插入节点，复杂度为O(logn)。map.find()的时间复杂度也是O(logn)。本质上是二叉平衡树中找到目标节点，假设目标节点在最深层找到，最坏时间复杂度则为O(logn)。最外层for循环O(n)。因此时间复杂度为O(nlogn)。

vector<int> twoSum_1(vector<int>& nums, int target) {
        multimap<int,int> maps;
        multimap<int,int>::iterator it;
        vector<int> result;
        for(int i=0;i<nums.size();i++) {
            if(i==0){
                maps.insert({nums[i],i});
                continue;
            }
//            每次遍历的目标值
            int temp = target - nums[i];
            it = maps.find(temp);
//            没有找到目标值
            if (it== maps.end())
                maps.insert({nums[i], i});
            else {
                    result.push_back(it->second);
                    result.push_back(i);
                    return result;
            }
        }
        return result;
    }