【LeetCode】Longest Substring Without Repeating Characters(无重复字符的最长子串)
2024-09-02 23:33:47
这道题是LeetCode里的第3道题。
题目描述:
给定一个字符串,请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3。
示例 2:
输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b",所以其长度为 1。
示例 3:
输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke",所以其长度为 3。 请注意,你的答案必须是 子串 的长度,"pwke"是一个子序列,不是子串。
这题可以使用双指针解题,但是不推荐,最好理解的方法就是我这种建立哈希表。但是呢,哈希表可以和双指针一起使用,节约一半的时间。哈希表的用途在于记录该字符是否出现过。
解题代码:
class Solution {
public int lengthOfLongestSubstring(String s) {
if(s.equals(""))return 0;
int maxLength = 0,len = 0;
int[] hashMap = new int[128];
int i=0,j=1;
hashMap[s.charAt(i)] = 1;
len++;
while(i < s.length() && j < s.length()) {
while(j < s.length()) {
if(hashMap[s.charAt(j)] == 1) {
hashMap[s.charAt(i)] = 0;
i++;
len = j - i + 1;
if(len > maxLength)maxLength = len;
hashMap[s.charAt(i)] = 1;
if(j<=i)j = i+1;
break;
}
hashMap[s.charAt(j)] = 1;
//len++;
j++;
}
}
len = j - i;
if(len > maxLength)maxLength = len;
return maxLength;
}
}
提交结果:
个人总结:
双指针:
class Solution {
public int lengthOfLongestSubstring(String s) {
if(s == null || s.length() == 0) return 0;
int start = 0, max = 1;
char[] str = s.toCharArray();
for(int j = 1; j < s.length(); j++) {
for(int i = start; i < j; i++){
if(str[i] == str[j]) {
start = i + 1;
break;
}
}
max = Math.max(j - start + 1, max);
}
return max;
}
}
双指针的基本思想就是确定开始遍历的字符位置。
最新文章
- asp.net mvc4 Html.BeginForm表单提交
- redhat安装VMware tools的方法
- 32个触发事件XSS语句的总结
- ==与equal在java中应用的感悟
- c++复习一:复数运算的简单实现。
- RabbitMQ 3.6 安装
- dagli最早干了这样一件事儿 Localization of Cardiac-Induced Signal Change in fMRI
- Android 二维码扫描与生成
- 关于mysql授权账号权限时的空密码问题
- iScroll 下拉刷新
- S2_SQL_第四章
- AI数据分析(一)
- Scala基础学习(一、数据类型)
- Oracle 系统调优
- Task任务的屏障机制
- Delphi 中的 XMLDocument 类详解(10) - 判断节点类型: 支节点、叶节点、文本节点、空节点
- 背水一战 Windows 10 (73) - 控件(控件基类): UIElement - 拖放的基本应用, 手动开启 UIElement 的拖放操作
- Linux免密码登录设置 &;&; 设置快捷键
- java Scanner和Random的Demo
- java图片操作--生成与原图对称的图片
热门文章
- Linux下安装maven和nexus
- linux服务器免密钥登录
- LeetCode Valid Parentheses 有效括号
- Android(java)学习笔记83:各种边距设置
- AngularJs学习笔记-表单处理
- GCH文件
- java程序换图标
- 转+更新 Graphviz 教程,例子+ 高级应用 写代码,编程绘制架构图(分层拓扑图) 转自官网
- 使用Servlet根据浏览器request的get方法获取值,将磁盘中与之对应的json数据删除的方法
- 32-1题:不分行从上到下打印二叉树/BFS/deque/queue