[LeetCode] Daily Practice 1 两数之和(Two Sum)-阿南达文事网

[LeetCode] Daily Practice 1 两数之和(Two Sum)

原文链接

题目来源:
力扣（LeetCode)

题目描述 📑

给定一个整数数组 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]

示例2:

输入：nums = [3,3], target = 6
输出：[0,1]

解题思路 🤔

思路一暴力解法–遍历

那道题先用最简单直接的方式遍历解一下.

先审下题目,即有一个数组,需要从中取出两个数,然后返回两个数的下标.

最直接能想到的方式就是两层嵌套循环,分别取两个数,相加后判断是否等于target,等于则返回两数下标即可.

很简单直接,无需多做解释.

但是他的时间复杂度比较高为: O(n^2)

思路一 Code

class Solution {
public:vector<int> twoSum(vector<int>& nums, int target) {int size=nums.size();for(int fir_idx=0;fir_idx<size-1;++fir_idx){for(int sec_idx=fir_idx+1;sec_idx<size;++sec_idx){if(nums[fir_idx]+nums[sec_idx]==target){return {fir_idx,sec_idx};}}}return {};}
};

思路一提交结果

提交3次结果如下

提交结果	执行用时	内存消耗	用时击败	内存击败
通过	260 ms	9.9MB	39.97%	74.95%
通过	276 ms	9.9MB	33%	87%
通过	352 ms	9.8MB	15%	98%

思路二 LUT

暴力解完后,咱们来换一换思路,来看一下有没有可能把时间复杂度降低下来呢

再来审题,首先,我们先取一个值fir_val ,取值过程是一个遍历的过程,此时下标也是知道到,假设为fir_idx.

此时我们有了第一个值,第二个值要如何取得呢?OK 让我们再审下题:

题目需要我们找到两个值,满足:

fir_val+sec_val=target.

做一下简单的变化:

sec_val=target-fir_val.

💡OK!!!前面我们已经有了 fir_val,经过一个简单的减法,满足题目条件的第二个值是多少也就确定了.

伪代码如下:

class Solution {
public:vector<int> twoSum(vector<int>& nums, int target) {...int size=nums.size();int sec_val=0;int sec_idx=0;for(int fir_val : nums){sec_val=target-nums[fir_idx];if(false==nums_has_sec_val()){continue;}sec_idx=get_val_idx();if(sec_idx==fir_idx){//因为题目不允许输出相同下标continue;}return {fir_idx,sec_idx};}return {};}
};

接下来,只要确定下,题目输入的数组中是否含有sec_val这个数值,并获取到这个sec_idx;

现在问题转换成了:如何确定,输入中含有sec_val,且获取到下标sec_idx;

查询某个key(即sec_val)的对应value(即sec_idx),这不就是查表么!

问题就变成了了,生成一张val-idx的表,即LUT,然后通过LUT确认输入是否含有sec_val,并查到sec_idx.

伪代码如下:

class Solution {
public:vector<int> twoSum(vector<int>& nums, int target) {...gen_LUT();int size=nums.size();int sec_val=0;int sec_idx=0;for(int fir_val : nums){sec_val=target-nums[fir_idx];if(LUT(sec_val,sec_idx).unfinded){continue;}if(sec_idx==fir_idx){//因为题目不允许输出相同下标continue;}return {fir_idx,sec_idx};}return {};}
};

如何实现LUT?,遍历一遍输入的数组,把val:index 插入到一个 map中就可以了;

在这个思路里,分别需要进行两个循环,这两个循环最大循环次数都小于 n(输入数组的大小),并且两次循环并不嵌套,故最坏情况下,需要进行的循环次数小于2n.

故时间复杂度为:O(2n)

思路二 Code

class Solution {
public:vector<int> twoSum(vector<int>& nums, int target) {int size=nums.size();std::map<int,int> lut;//value:indexfor(int idx=0;idx<size;++idx){lut[nums[idx]]=idx;}        int sec_val=0;for(int fir_idx=0;fir_idx<size;++fir_idx){sec_val=target-nums[fir_idx];if(lut.find(sec_val)!=lut.end()&&lut[sec_val]!=fir_idx){return {fir_idx,lut[sec_val]};}}return {};}
};

思路二提交结果

提交3次结果如下

提交结果	执行用时	内存消耗	用时击败	内存击败
通过	12 ms	12.3MB	67.95%	5.04%
通过	8 ms	12.2MB	91.26%	5.04%
通过	16 ms	12.2MB	51.11%	5.04%

可以看到用时上的提升特别大,从260ms以上降低到了 10ms左右,当然代价就是内存消耗增加了,原因在于额外维护了一个Map类型的LUT导致了空间消耗的增加,典型的拿空间换时间!

原文链接