hot100🔥踩点

class Solution {
public:
	vector<int> twoSum(vector<int>& nums, int target) {
	    unordered_map <int,int> hash;
	    for (int i=0;i<nums.size();i++) {
	        auto it = hash.find(target-nums[i]);
	        if (it!=hash.end()) {
	            return {it->second, i};
	        }
	        hash[nums[i]]=i;
	    }
	    return {};
	}
}

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        unordered_map<string, vector<string>> mp;
        for (string s: strs) {
            string key=s;
            sort(key.begin(), key.end());
            mp[key].push_back(s);
        }
        vector<vector<string>> ans;
        for (auto [k,v]: mp) {
            ans.push_back(v);
        }
        return ans;
    }
};

class Solution {
public:
	int longestConsecutive(vector<int>& nums) {
	    unordered_set<int> st;
	    for(int num:nums) {
	        st.insert(num);
	    }
	    int ans=0;
	    for(int num:st) {
	        if(!st.count(num-1)) { // 从未出现过它的前一位，起始数字
	            int curLen=1;
	            int curNum=num;
	            while(st.count(curNum+1)) {
	                curLen++;
	                curNum+=1;
	            }
	            ans=max(ans,curLen);
	        }
	    }
	    return ans;
	}
};

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
	    int r=0, n=nums.size(); // r为最终数组里第一个0的下标
	    for (int l=0;l<n;l++) {
	        if (nums[l]!=0) {
	           swap(nums[l],nums[r]);
	           r++;
	        }
	    }
    }
};

class Solution {
public:
	int maxArea(vector<int> &height) {
	    int n=height.size();
	    int l=0, r=n-1;
	    while(l<r) {
	        ans=max(ans, (max(height[l], height[r]) * (r-l));
	        if (height[l]<height[r]) l++;
	        else r--;
	    }
	    return ans;
	}
}

class Solution {
public:
	vector<vector<int>> threeSum(vector<int>& nums) {
	    vector<vector<int>> res;
	    if(nums.size()<3) return res;
	    sort(nums.begin(),nums.end());
	    for(int i=0;i<nums.size();i++) {
	        // 新的一轮
	        if(nums[i]>0) break;
	        if(i>0 && nums[i]==nums[i-1]) continue; // 去重
	        int target=-nums[i];
	        int l=i+1,r=nums.size()-1;
	        while(l<r) {
	            if(nums[l]+nums[r]==target) {
	                res.push_back({nums[i],nums[l],nums[r]});
	                while(l<r && nums[l]==nums[l+1]) l++;
	                while(l<r && nums[r]==nums[r-1]) r--;
	                l++,r--;
	            }else if(nums[l]+nums[r]<target) {
	                l++;
	            }else r--;
	        }
	    }
	    return res;
	}
}

class Solution {
public:
	int trap(vector<int>& height) {
	    int n=height.size();
	    vector<int> left(n), right(n);
	    left[0]=height[0];
	    right[n-1]=height[n-1];
	    for (int i=1;i<n;i++) {
	        left[i]=max(left[i-1],height[i]);
	    }
	    for (int i=n-2;i>=0;i--) {
	        right[i]=max(right[i+1],height[i]);
	    }
	    int sum=0;
	    for (int i=0;i<n;i++) {
	        sum+=min(left[i],right[i])-height[i];
	    }
	    return sum;
	}
}

class Solution {
public:
	int lengthOfLongestSubstring(string s) {
	    unordered_set <char> mp;
	    int r=0, ans=0;
	    for (int l=0;l<s.size();l++) {
	        if (l>0) mp.erase(s[l-1]); // 重复的字符，在mp中去掉它
	        while (r<s.size() && !mp.count(s[r])) {
	            mp.insert(s[r]);
	            r++;
	        }
	        ans=max(ans, r-l);
	    }
	    return ans;
	}
}

class Solution {
public:
	vector<int> findAnagrams(string s, string p) {
	    vector<int> sCount(26),pCount(26);
	    int ns=s.size(), np=p.size();
	    if (ns<np) return vector<int> {};
	    for (int i=0;i<np;i++) {
	       pCount[p[i]-'a']++; //填充指定字母表数组
	       sCount[s[i]-'a']++; //填充初始窗口数组
	    }
	    vector<int> ans;
	    if (pCount==sCount) ans.push_back(0);
	    for (int i=0;i<ns-np;i++) {
	        sCount[s[i]-'a']--;
	        sCount[s[i+np]-'a']++;
	        if(pCount==sCount) ans.push_back(i+1);
	    } 
	    return ans;
	}
}

class Solution {
public: 
	int subarraySum(vector<int>& nums,int k) {
	    unordered_map<int,int> mp;
	    mp[0]=1;
	    int pre=0,count=0;
	    for (int x:nums) {
	        pre+=x;
	        if (mp.find(pre-k)!=mp.end()) {
	            count+=mp[pre-k];
	        }
	        mp[pre]++;
	    }
	    return count;
	}
}

class Solution {
public:
	vector<int> maxSlidingWindow(vector<int>& nums, int k) {
	    int n=nums.size();
	    priority_queue<pair<int,int>> q; // {val, index}
	    for(int i=0;i<k;i++) { // 初始化填充窗口
	        q.push({nums[i],i});
	    }
	    vector<int> res;
	    res.push_back(q.top().first);
	    for(int i=k;i<n;i++) { // 移动窗口！
	        q.push({nums[i],i});
	        while(q.top().second<=i-k) { // 当前队头元素已经不在滑动窗口里咯！删掉删掉
	            q.pop();
	        }
	        res.push_back(q.top().first); // 添加当前窗口里的最大值进答案数组
	    }
	    return res;
	}
}

class Solution {
public:
	string minWindow(string s, string t) {
	    unordered_map<char,int> need, window; // 固定值和移动窗口
	    for (char x:t) {
	        need[x]++; // 填充固定值
	    }
	    int left=0, right=0; // 左右指针
	    int valid=0; // 满足的字符个数
	    int start=0, len=INT_MAX;
	    while(right<s.size()) {
	        // 取值判断移动右指针
	        char c=s[right];
	        right++;
	        if (need.count(c)) {
	            window[c]++;
	            if(window[c]==need[c]) { // 如果和目标的字符数一样则++
	                valid++;
	            }
	        }
	        while(valid==need.size()) { // 如果字符数和需求的一样了则左移指针
	            // 此处判断值
	            if (right-left<len) {
	                start=left;
	                len=right-left;
	            }
	            // 取值判断移动左指针
	            char d=s[left];
	            left++;
	            if (need.count(d)) {
	                if (window[d]==need[d]) {
	                    valid--;
	                }
	                window[d]--;
	            }
	        }
	    }
	    return len==INT_MAX?"":s.substr(start,len);
	}
}

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int n=nums.size(), ans=0;
        vector<int> dp(n);
        dp[0]=nums[0];
        ans=dp[0];
        for (int i=1;i<n;i++) {
            dp[i]=max(dp[i-1]+nums[i], nums[i]);
            ans=max(ans,dp[i]);
        }
        return ans;
    }
}