hot100_3.无重复字符的最长子串
给定一个字符串 s ，请你找出其中不含有重复字符的 最长 子串 的长度。
示例 1:
输入: s = "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
示例 2:
输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
示例 3:
输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
提示：
-
0 <= s.length <= 5 * 104 -
`s` 由英文字母、数字、符号和空格组成
#include<iostream>
#include<string>
#include<algorithm>
#include<map>
using namespace std;
//双指针解法
class Solution{public:int lengthOfLongestSubstring(string s){int startIndex = 0;int endIndex = 0;int currentLength = 0;int maxLength = 0;while (endIndex < s.length()){char pendingChar = s[endIndex];//判断待处理字符串是否在当前子串中存在for (int i = startIndex; i < endIndex; i++){//如果子串中已经存在待处理字符if (pendingChar == s[i]){ startIndex = i + 1; //把start指针跳转至子串中重复字符下一个位置currentLength = endIndex - startIndex;break;}}endIndex++;currentLength++;maxLength = max(maxLength, currentLength);}return maxLength;}
};//滑动窗口解法 class Solution {public:int lengthOfLongestSubstring(string s) {unordered_map<char, int> window;int len = 0;int left = 0, right = 0;while(right < s.size()) {char c = s[right];right++;window[c]++;while(window[c] > 1) { //若在窗口子串中找到该字符，说明新的窗口子串不符合条件，则将窗口最左端元素移出，直到将除当前位置的最后一次出现的该字符移除窗口，将新字符加入窗口中后，继续向下遍历；char d = s[left];left++;window[d]--;}len = max(len, right - left);}return len;}};int main(){string str = "dvdb";Solution A;cout << A.lengthOfLongestSubstring(str) << endl;return 0;
}
hot100_438.找到字符串中所有字母异位词
给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。
示例 1:
输入: s = "cbaebabacd", p = "abc"
输出: [0,6]
解释:
起始索引等于 0 的子串是 "cba", 它是 "abc" 的异位词。
起始索引等于 6 的子串是 "bac", 它是 "abc" 的异位词。
示例 2:
输入: s = "abab", p = "ab"
输出: [0,1,2]
解释:
起始索引等于 0 的子串是 "ab", 它是 "ab" 的异位词。
起始索引等于 1 的子串是 "ba", 它是 "ab" 的异位词。
起始索引等于 2 的子串是 "ab", 它是 "ab" 的异位词。
提示:
-
1 <= s.length, p.length <= 3 * 104 -
`s` 和 `p` 仅包含小写字母
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
using namespace std;
// class Solution {
// public:
// vector<int> findAnagrams(string s, string p) {// int hash_s[26] = {0},hash_p[26] = {0};
// vector<int>ret;// //初始化哈希表
// for(auto ch:p)
// {
// hash_p[ch - 'a']++;
// }
// int len = p.size();
// int count = 0;//存放有效个数
// for(int left = 0,right = 0;right < s.size();right++)
// {
// //进窗口
// char in = s[right];//right的更新在循环结束后，所以这里不++，先不移动right
// if(++hash_s[in - 'a'] <= hash_p[in-'a'])//先更新哈希表再比较
// {
// count++;
// }
// //判断
// if(right-left+1 > len) //因为是窗口大小是固定的，所以用if语句即可
// {
// //出窗口
// char out = s[left++];
// if(hash_s[out - 'a']-- <= hash_p[out - 'a'])//先比较再更新哈希表
// {
// count--;
// }// }
// //更新
// if(count == len)//有效数一致 ----- 为字母异位词
// {
// ret.push_back(left);
// }// }
// return ret;
// }
// };class Solution{public:vector<int> findAnagrams(string s, string p){vector<int> result;int flag[26] = {0};int pLen = p.length();for(int i = 0; i < pLen; i++){flag[p[i] - 'a']++;} int l = -1, r = pLen - 1;while(r < s.length()){ l++;r = l + pLen - 1;int FF[26] = {0};copy(flag, flag + 26, FF);bool bb = true;for(int i = l; i <= r; i++){if(i >= s.length()){bb = false;break;}if(flag[s[i] - 'a'] == 0){l = i;bb = false;break;}else if(FF[s[i] - 'a'] < 1){bb = false;break;}else {FF[s[i] - 'a']--;}}if(bb) result.push_back(l);}return result;}};int main(){string s = "cbaebabacd";string p = "abc";Solution A;vector<int> result = A.findAnagrams(s, p);cout << "[";for(int i = 0; i < result.size(); i++){cout << result[i] << ", ";}cout<< "]" << endl;return 0;
}
