题号：1
难度：Easy
链接：两数之和

题目

给定一个整数数组 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) 的算法吗？

思路

暴力解法不必说，遍历一遍组合即可，无需额外空间，时间复杂度$O(n^2)$。

要降低时间复杂度，我的思路是从查找差来考虑：

首先对序列进行排序，然后依次确定一个数为num1，由于target确定，num2即为target-num1。

之后从删去num1的序列中查找num2，此时使用二分法来查找，则整体时间复杂度为$O(n*logn)$。

如果一轮查找失败，则将num1插回序列，继续以下一位为num1进行查找即可。

如果查找成功，则锁定了num1和num2的组合，因为要返回的是两者在原序列中的位置，则再在原序列中进行一次线性查找即可（无序序列不能用二分法）。

由于线性查找时间复杂度为$n$，且只会进行一次，在数据量大的情况下对整体时间复杂度的影响可以忽略。

代码

#include <vector>
#include <algorithm>

using std::equal_range;
using std::vector;
using std::sort;

class Solution
{
public:
    vector<int> twoSum(vector<int> &nums, int target)
    {
        vector<int> ans; //作为函数的返回值

        //对nums进行排序，因为最后要返回原位置，所以另行构造
        vector<int> nums_sort(nums.begin(),nums.end());
        sort(nums_sort.begin(),nums_sort.end());

        int num1;
        int num2;
        //依次选定一个元素作为num1，则num2=target-num1
        //然后二分法查找num2是否存在
        //若存在则在原序列查找num1和num2位置并返回
        for (int i = 0; i < nums_sort.size(); ++i)
        {
            //确定num1和num2，然后删除num1
            auto iter = nums_sort.begin();
            advance(iter,i);
            num1 = *iter;
            num2 = target-num1;
            iter = nums_sort.erase(iter);
            //二分法查找，对数时间复杂度
            auto ansIter = lower_bound(nums_sort.begin(),nums_sort.end(),num2);

            //只在成功配对num1和num2的情况下进行的线性查找
            //时间复杂度n，对整体而言无影响
            if(*ansIter==num2){
                for(int j = 0;j < nums.size();++j){
                    if(nums[j]==num1) ans.insert(ans.end(),j);
                    else if (nums[j]==num2) ans.insert(ans.end(),j);
                    //两个位置都已经确定，可以直接跳出
                    if(ans.size()==2) break;
                }
                //返回值确定，跳出循环
                break;
            }
            //配对失败，把num1重新插回序列
            nums_sort.insert(iter,num1);
        }
        return ans;
    }
};

提交结果

还能接受，有待改进。