LeetCode Day1: 两数之和

发布于 2022-08-21  192 次阅读


题号: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进行查找即可。

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

由于线性查找时间复杂度为$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;
    }
};

提交结果

还能接受,有待改进。