【算法刷题】有人相爱,有人夜里开车看海,有人leetcode第一题都做不出来

都做不出来"/>

【算法刷题】有人相爱,有人夜里开车看海,有人leetcode第一题都做不出来

文章目录

• 1. 两数之和
• • 方法1:暴力 -O(N^2)
  • 方法2:哈希表

题目标题是copy官网评论第一条的啦~觉得很有趣就用来当标题了！侵权删

1. 两数之和

/

方法1:暴力 -O(N^2)

class Solution {
public:vector<int> twoSum(vector<int>& nums, int target) {int i = 0;int j = 0;vector<int> ans;for(int i = 0;i<nums.size();i++){//j从i+1位置开始找for(int j = i+1;j<nums.size();j++){//寻找目标值targetif(nums[i]+nums[j] == target){ans.push_back(i);ans.push_back(j);break;}}}return ans;}
};

方法2:哈希表

使用map,key-value为:元素值-下标
遍历到i下标位置的元素x,先查找map中是否含target-x这个元素

• 如果有:那么x + target-x = target, 返回此时i位置和此时map中该元素的第二个成员
• 如果没有:就把当前{i,x}新插入到map中,为后序寻找做准备

class Solution {
public:vector<int> twoSum(vector<int>& nums, int target) {map<int,int> m;//值nums[i]- 下标ivector<int> v;//存放结果for(int i = 0;i<nums.size();i++){//当前元素nums[i]//在map中查找是否有target-nums[i]这个值auto it = m.find(target-nums[i]);if(it != m.end()) {//如果找到了,返回当前i位置和map中此元素第二个成员的下标v.push_back(it->second);v.push_back(i);break;}//没有找到,在map中插入键值对:当前元素值 - 当前元素下标m.insert(make_pair(nums[i],i));   //没有找到 -> 插入当前元素}return v;//返回空容器}
};