LeetCode 1.两数之和

LeetCode 1.两数之和

解法一:暴力求解

分析:

直接两层循环,遍历数组:

第一层循环确定一个数n1,然后第二层循环中判断数组中是否存在target - n1,如果存在,将{n1,n2}返回。

O(n^2),会超时。

代码:

vector<int> twoSum_force(vector<int>& nums, int target) {
    vector<int> result(2);
    for(int i=0; i<nums.size(); i++) {
        int minus = target - nums[i];
        for(int j=i+1; j<nums.size(); j++) {
            if(nums[j] == minus) {
                result[0]=i;
                result[1]=j;
                return result;
            }
        }
    }
    return result;
}

解法(思路)二:

分析:

先排序,然后利用双指针,左右夹逼寻找,假如两个指针当前为ijsum = nums[i]+nums[j]

  • 如果sum<target,即两数的和大小不够大,让i++
  • 如果sum>target,即两数的和过大,让j--;
  • 如果sum == target,即找到了这两个数。

排序O(nlogn),左右夹逼O(n),最终为 O(nlogn)。

如果本题结果是返回两个数,这个方法就可以使用

但是本题要求的是返回下标,排序后下标已经变化,所以行不通。

解法三:哈希表

分析:

在解法一中思想是两层循环,第一层循环确定一个数n1,去找数组中有没有另一个数n2,与n1相加结果为target。

解法一超时的原因,就是每次去找这样的一个n2,都需要遍历一遍数组,即O(n)。
最坏情况下,对数组中的每个元素都去找一遍有没有另一个数相加为target,这样就导致时间复杂度为O(n^2)。

能不能利用一种机制,加速n2的查找,我们很容易可以想到,哈希表的查找时间在O(1)。

所以,在哈希表中存储数组中所有元素的下标,只需要一次遍历,遍历到num时,直接去哈希表中找,有没有target-num,这样就可以让整个查找的时间复杂度降至O(n)。

tips:

如果找到了结果,需要以vector的形式返回的两个数的下标为i1,i2
//可以直接返回:
return {i1,i2};

//来代替下面的:
vector<int> result(2);
result[0] = i1;
result[1] = i2;
return result;

代码:

vector <int> twoSumHash(vector<int>& nums, int target) {
    //vector <int> result(2);
    unordered_map<int,int> hashtable;
    for(int i =0 ; i<nums.size(); i++) {
        int minus = target - nums[i];
        if(hashtable.count(minus)) {
            //result[0]=hashtable[minus];
            //result[1]=i;
            return {hashtable[minus],i};
        }
        hashtable[nums[i]]=i;
    }
    return {};
}
上一篇:Golang笔记之函数


下一篇:2021年N1叉车司机考试APP及N1叉车司机复审考试