做动效的网站,wordpress禁止右键弹出菜单,网站开发实施方案,网站建设合同 域名本文主要讲解无重复字符的最长字串的要点与细节#xff0c;根据步骤一步步走更方便理解
c与java代码如下#xff0c;末尾
具体要点#xff1a;
1. 区分一下子串和子序列 子串#xff1a;要求元素在母串中是连续地出现 子序列#xff1a;不要求连续 2. 题目中有两个核心…本文主要讲解无重复字符的最长字串的要点与细节根据步骤一步步走更方便理解
c与java代码如下末尾
具体要点
1. 区分一下子串和子序列 子串要求元素在母串中是连续地出现 子序列不要求连续 2. 题目中有两个核心要点无重复最长 无重复我们可以想到哈希表来解决哈希表用来判断一个元素是否出现过 最长我们可以利用滑动窗口的思路来解决滑动窗口通常用来解决某种连续性子序列条件 3. 我们选用哪种哈希表来实现呢通过思考我们只需要知道元素是否出现过不需要记录其他信息例如索引、次数等所以我们可以使用set来解决 4. 解决了无重复的问题我们思考一下滑动窗口具体应该怎么实现 滑动窗口通常都是两个指针一个right一个left 开始时我们先移动right判断条件是right始终不越界 right的值始终没有出现过 即 while (right s.size() hashset.find(s[right]) hashset.end()) 移动right并加入set中 即 hashset.insert(s[right]); right; 直到right不能再移动后我们记录最大长度并移动一次left同时把left的值从set中删除 即 //更新最大长度 result max(result, right - left); //删除left并移动left hashset.erase(s[left]); left; 至此实现一轮滑动每一轮都只移动一次left c代码
class Solution {
public:int lengthOfLongestSubstring(string s) {int result 0;//定义滑动窗口的两个指针int left 0, right 0;//定义一个set去重unordered_setchar hashset;while (right s.size()) {//不断移动rightwhile (right s.size() hashset.find(s[right]) hashset.end()) {hashset.insert(s[right]);right;}//更新最大长度result max(result, right - left);//移动lefthashset.erase(s[left]);left;}return result;}
};
java代码
class Solution {public int lengthOfLongestSubstring(String s) {//滑动窗口int right 0, left 0;int result 0;//定义set防止重复HashSetCharacter map new HashSetCharacter();//特殊情况0和1if (s.length() 0 || s.length() 1) {return s.length();}while (s.length() right) {//right位置如果没有出现过就addwhile (s.length() right !map.contains(s.charAt(right))) {map.add(s.charAt(right));right;}result Math.max(result, right - left);//right移动到不能移动就开始移动leftmap.remove(s.charAt(left));left;}return result;}
}
