LeetCode热题100-1——两数之和

目录

• 前言
• 正文
• 参考

前言

正文

题目

未看题解时，解题的思路

1. 首先，感觉O(N2)得方法是肯定可以解决的，但就是不知道会不会超时间复杂度。
2. 错误思路：应该还有个思路2：就是先排个序，从首尾逐渐向中间靠近。错了，这题不能排序，因为它要返回的值是下标，不能瞎排序。

自己实现的代码
code

class Solution {
public:vector<int> twoSum(vector<int>& nums, int target) {//先写个O(n2)的方法把vector<int> arr;if(nums.size()==0)return arr;//特殊情况的返回条件要判定for(int i = 0;i<nums.size();i++){for(int j = i+1;j<nums.size();j++)//不要是相同数{if(nums[i]+nums[j]==target){arr.push_back(i);arr.push_back(j);return arr;//这里直接返回即可}}}return arr;//若没有找到，也要有一个返回值}
};

看了题解后解题的思路
**正确思路：**注意到方法一的时间复杂度较高的原因是寻找 target - x 的时间复杂度过高。因此，我们需要一种更优秀的方法，能够快速寻找数组中是否存在目标元素。如果存在，我们需要找出它的索引。使用哈希表，可以将寻找 target - x 的时间复杂度降低到从 O(N)O(N) 降低到 O(1)O(1)。这样我们创建一个哈希表，对于每一个 x，我们首先查询哈希表中是否存在 target - x，然后将 x 插入到哈希表中，即可保证不会让 x 和自己匹配。

标准答案的代码
code

class Solution {
public:vector<int> twoSum(vector<int>& nums, int target) {//基本就是直接先取出某个元素的和减该值vector<int> res;if(nums.size()==0)return res;map<int,int> map;for(int i = 0;i<nums.size();i++){int t = target-nums[i];if(map.count(nums[i])){res.push_back(map[nums[i]]);//反倒这个代表的才是nums[i]的下标res.push_back(i);//这个i代表的就已经是t这个元素的nums下标了}else{map[t] = i;}}return res;}
};

参考

1. 力扣热题100-1：两树之和

LeetCode热题100-1——两数之和

目录

• 前言
• 正文
• 参考

前言

正文

题目

未看题解时，解题的思路

1. 首先，感觉O(N2)得方法是肯定可以解决的，但就是不知道会不会超时间复杂度。
2. 错误思路：应该还有个思路2：就是先排个序，从首尾逐渐向中间靠近。错了，这题不能排序，因为它要返回的值是下标，不能瞎排序。

自己实现的代码
code

class Solution {
public:vector<int> twoSum(vector<int>& nums, int target) {//先写个O(n2)的方法把vector<int> arr;if(nums.size()==0)return arr;//特殊情况的返回条件要判定for(int i = 0;i<nums.size();i++){for(int j = i+1;j<nums.size();j++)//不要是相同数{if(nums[i]+nums[j]==target){arr.push_back(i);arr.push_back(j);return arr;//这里直接返回即可}}}return arr;//若没有找到，也要有一个返回值}
};

看了题解后解题的思路
**正确思路：**注意到方法一的时间复杂度较高的原因是寻找 target - x 的时间复杂度过高。因此，我们需要一种更优秀的方法，能够快速寻找数组中是否存在目标元素。如果存在，我们需要找出它的索引。使用哈希表，可以将寻找 target - x 的时间复杂度降低到从 O(N)O(N) 降低到 O(1)O(1)。这样我们创建一个哈希表，对于每一个 x，我们首先查询哈希表中是否存在 target - x，然后将 x 插入到哈希表中，即可保证不会让 x 和自己匹配。

标准答案的代码
code

class Solution {
public:vector<int> twoSum(vector<int>& nums, int target) {//基本就是直接先取出某个元素的和减该值vector<int> res;if(nums.size()==0)return res;map<int,int> map;for(int i = 0;i<nums.size();i++){int t = target-nums[i];if(map.count(nums[i])){res.push_back(map[nums[i]]);//反倒这个代表的才是nums[i]的下标res.push_back(i);//这个i代表的就已经是t这个元素的nums下标了}else{map[t] = i;}}return res;}
};

参考

1. 力扣热题100-1：两树之和