小说网站开发实录,嘉兴网页制作网站排名,wordpress导入大小.h,八年级信息技术网页制作原题链接
解题思路:
(双指针扫描) O(n)#xff0c;双指针主要作用是维护一段区间 定义两个指针 i,j(ij)#xff0c;表示当前扫描到的子串是 [i,j] (闭区间)。扫描过程中维护一个哈希表unordered_mapchar,int hash#xff0c;表示 [i,j]中每个字符出现的次数。…原题链接
解题思路:
(双指针扫描) O(n)双指针主要作用是维护一段区间 定义两个指针 i,j(ij)表示当前扫描到的子串是 [i,j] (闭区间)。扫描过程中维护一个哈希表unordered_mapchar,int hash表示 [i,j]中每个字符出现的次数。 线性扫描时每次循环的流程如下
指针 j 向后移一位, 同时将哈希表中 s[j] 的计数加一: hash[s[j]]; 假设 j 移动前的区间 [i,j] 中没有重复字符则 j 移动后只有 s[j]可能出现2次。因此我们不断向后移动 i直至区间 [i,j]中 s[j]的个数等于1为止 复杂度分析由于 i,j均最多增加n次且哈希表的插入和更新操作的复杂度都是 O(1)因此总时间复杂度 O(n). class Solution {
public:
int lengthOfLongestSubstring(string s) {unordered_mapchar,inthash;int res 0;for (int i 0, j 0; j s.size(); j ){hash[s[j]] ;while (hash[s[j]] 1) {//此处--修改string中各位置的对应value减少1,当while停止的时候i为与j处重复的地方hash[s[i ]] -- ; }//此处记录当前字符串中的最大字串值,因为数组下标从0开始所以需要加1res max(res, j - i 1);}return res;
}
};
