1. 两数之和
暴力：{i,j}直接返回vector<int>
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
for(int i=0;i<nums.size();i++){
for(int j=i+1;j<nums.size();j++){
if(nums[i]+nums[j]==target){
//大括号里面直接写元素->vector
return {i,j};
}
}
}
return {};
}
};哈希表：
map: 红黑树 具有自动排序的功能，是非严格的二叉搜索树。map内部的所有元素都是有序的，使用中序遍历可将键值按照从小到大遍历出来。插入的时间是O(logn),查询时间是O(logn)。可以支持所有类型的键值对
unordered_map: 哈希表（也叫散列表，通过关键码值映射到Hash表中一个位置来访问记录，查找的复杂度是O(1)。无序的（海量数据广泛应用）。插入的时间是O(logn),查询时间是O(1)。它的key只能是int、double等基本类型以及string，而不能是自己定义的结构体。
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int, int> hashtable;
for (int i = 0; i < nums.size(); ++i) {
auto it = hashtable.find(target - nums[i]);
if (it != hashtable.end()) {
return {it->second, i};
}
hashtable[nums[i]] = i;
}
return {};
}
};2. 字母异位词分组
class Solution {
public:
vector<vector<string>> groupAnagrams(vector<string>& strs) {
unordered_map<string,int> mp;
vector<vector<string>> res;
int num=-1;
for(auto i:strs){
string s=i;
sort(s.begin(),s.end());
if(mp.count(s)==0){
mp[s]=++num;
res.push_back({});
}
res[mp[s]].push_back(i);
}
return res;
}
};官方：（还有一种是计每个字母出现的次数）
class Solution {
public:
vector<vector<string>> groupAnagrams(vector<string>& strs) {
unordered_map<string, vector<string>> mp;
for (string& str: strs) {
string key = str;
sort(key.begin(), key.end());
mp[key].emplace_back(str);
}
vector<vector<string>> ans;
for (auto it = mp.begin(); it != mp.end(); ++it) {
ans.emplace_back(it->second);
}
return ans;
}
};3. 最长连续序列
在未排序的数组中找到最长的连续序列。时间复杂度On，数字范围整个INT。
第一种：不断更新最长连续序列的左右两个端点 记录的最长连续序列值。
class Solution {
public:
int longestConsecutive(vector<int>& nums) {
unordered_map<int,int> mp;
int mx=0;
for(auto i:nums){
//未更新过的，已经在的话再更新会翻倍！
if(mp.count(i)) continue;
//找出当前数字左右两端的最长连续序列的长度
int l=0;
if(mp.count(i-1)) l=mp[i-1];
int r=0;
if(mp.count(i+1)) r=mp[i+1];
//更新当前节点
mp[i]=l+r+1;
mx=max(mx,mp[i]);
//更新当前节点所在的连续序列的左右两个端点的最长序列值，一定是最大的，因为在原来的基础上把左或右还有当前节点加上了！
//只需要告知最左右两个就可以，因为之后出现的数一定是未出现过的，在这些区间外的点！！
mp[i-l]=mp[i];
mp[i+r]=mp[i];
}
return mx;
}
};第二种：回溯，记录每个点能找到的最右端点。初始化为i+1。
class Solution {
public:
unordered_map<int,int> mp;
int find(int x){
if(!mp.count(x)) return x;
else return mp[x]=find(mp[x]);
}
int longestConsecutive(vector<int>& nums) {
for(auto i:nums) mp[i]=i+1;
int mx=0;
for(auto i:nums){
mx=max(mx,find(i)-i);
}
return mx;
}
};第三种：集合 直接找
class Solution {
public:
int longestConsecutive(vector<int>& nums) {
unordered_set<int> s;
for(auto i:nums){
s.insert(i);
}
int mx=0,now=0,cnt=0;
for(auto i:s){
if(!s.count(i-1)){
now=i;cnt=1;
while(s.count(now+1)){
now++;
cnt++;
}
}
mx=max(mx,cnt);
}
return mx;
}
};4. 移动零
class Solution {
public:
void moveZeroes(vector<int>& nums) {
int i=0,j=0,cnt=0;
for(i=0;i<nums.size();i++){
if(nums[i]!=0){
nums[j++]=nums[i];
}
else{
cnt++;
}
}
while(cnt--){
nums[j++]=0;
}
}
};5. 盛最多水的容器
双指针：分别指向最左和最右，尽量保留 越靠近边上的 并且 高的
即无论我们怎么移动右指针，得到的容器的容量都小于移动前容器的容量。也就是说，这个左指针对应的数不会作为容器的边界了，那么我们就可以丢弃这个位置，将左指针向右移动一个位置，此时新的左指针于原先的右指针之间的左右位置，才可能会作为容器的边界。
class Solution {
public:
int maxArea(vector<int>& height) {
int i=0,j=height.size()-1,mx=0,now=0;
while(i<j){
now=(j-i)*min(height[i],height[j]);
mx=max(mx,now);
if(height[i]<height[j]){
i++;
}
else{
j--;
}
}
return mx;
}
};6. 三数之和
如果我们固定了前两重循环枚举到的元素 a 和 b，那么只有唯一的 c 满足a+b+c=0。枚举一个元素 b′ 时，由于 b′>b，那么满足 a+b′+c′=0 的 c' 一定有 c′<c，即 c′在数组中一定出现在 c 的左侧。也就是说，我们可以从小到大枚举b，同时从大到小枚举 c，即第二重循环和第三重循环实际上是并列的关系。
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
sort(nums.begin(),nums.end());
int len=nums.size();
int k=len-1;
vector<vector<int>> res;
for(int i=0;i<len;i++){
if(i==0||nums[i-1]!=nums[i]){
k=len-1;
for(int j=i+1;j<len;j++){
if(j==i+1||nums[j-1]!=nums[j]){
while(k>j+1&&(nums[i]+nums[j]+nums[k])>0){
k--;
}
if(k>j&&(nums[i]+nums[j]+nums[k])==0){
res.push_back({nums[i],nums[j],nums[k]});
}
//cout<<nums[i]<<" "<<nums[j]<<" "<<nums[k]<<endl;
}
}
}
}
return res;
}
};7. 接雨水
计算当前位置能接的雨水，左右两边最高的 较小值 就是能到达的最高。文章来源：https://www.toymoban.com/news/detail-633134.html
class Solution {
public:
int trap(vector<int>& height) {
int len=height.size();
int left[200005],right[200005];
left[0]=height[0];
for(int i=1;i<height.size();i++){
left[i]=max(left[i-1],height[i]);
}
right[height.size()-1]=height[height.size()-1];
for(int j=height.size()-2;j>=0;j--){
right[j]=max(right[j+1],height[j]);
}
int sum=0;
for(int i=0;i<height.size();i++){
sum+=min(left[i],right[i])-height[i];
}
return sum;
}
};其实用两个常量记录就可以，不需要开数组文章来源地址https://www.toymoban.com/news/detail-633134.html
到了这里，关于Leetcode热题100的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
