国外做外汇网站交流,高端的丹阳网站建设,博物馆装饰设计公司,专业app网站建设哪家好一、题目描述 二、解题思路
借鉴以下题目思想#xff0c;使用双指针#xff0c;外层循环右侧指针移动#xff0c;内存循环左侧指针移动
字符串-最长不含重复字符的子字符串(mid)-CSDN博客文章浏览阅读622次#xff0c;点赞17次#xff0c;收藏4次。java刷题#xff1a;…一、题目描述 二、解题思路
借鉴以下题目思想使用双指针外层循环右侧指针移动内存循环左侧指针移动
字符串-最长不含重复字符的子字符串(mid)-CSDN博客文章浏览阅读622次点赞17次收藏4次。java刷题求最长不含重复字符的子字符串使用双指针结合题目要求减少左指针的移动次数降低程序执行复杂度这个题目很好值得好好理解。https://blog.csdn.net/hehe_soft_engineer/article/details/139320167题目要求K种字符则设置一个规模大小为K的hashset该hashset记录当前至多包含K种字符的子串所含的字符类型。
1.当hashset所含字符种类小于K时右指针。
2.当hashset所含字符种类等于K时 2.1当右指针指向的字符在hashset中右指针 2.2当右指针指向字符不在hashset中找到当前子字符串中最久未出现的字符定位到字符位置将左指针指向该字符后一个位置右指针以实现更新至多包含K种字符的子串。 3.如果当前子串长度变长了则更新记录最长长度的变量。
三、代码实现
import java.util.*;public class Solution {/*** 代码中的类名、方法名、参数名已经指定请勿修改直接返回方法规定的值即可** * param s string字符串 * param k int整型 * return int整型*/public int longestSubstring (String s, int k) {// 设置left和right双指针int left0,right0;HashSetCharacter charsetnew HashSet();charset.add(s.charAt(0));int maxLen0;for(;rights.length();right){if(charset.contains(s.charAt(right))){//此时不做操作}else{if(charset.size()k){//当前字符种类并没有达到k添加字符种类charset.add(s.charAt(right));}else{//此时需要从右侧开始找到第k次读取的字符(替换出set)int icounter0;int leftdeletIndexright-1;HashSetCharacter tmpcharsetnew HashSet();while(leftdeletIndexleft){if(!tmpcharset.contains(s.charAt(leftdeletIndex))){tmpcharset.add(s.charAt(leftdeletIndex));}if(tmpcharset.size()k){//此时leftdeletIndex就是需要移除的字符tmpcharset.clear();break;}leftdeletIndex--;}leftleftdeletIndex1;charset.remove(s.charAt(leftdeletIndex));charset.add(s.charAt(right));}}maxLenmaxLen(right-left1)?maxLen:(right-left1);}return maxLen;}
}
四、刷题链接
至多包含K种字符的子串_牛客题霸_牛客网
