前往小程序,Get更优阅读体验!
立即前往
发布
社区首页 >专栏 >3. Longest Substring Without Repeating Characters(HashSet + 双指针)

3. Longest Substring Without Repeating Characters(HashSet + 双指针)

作者头像
yesr
发布2019-03-14 13:02:42
发布2019-03-14 13:02:42
31900
代码可运行
举报
文章被收录于专栏:leetcode_solutionsleetcode_solutions
运行总次数:0
代码可运行

Longest Substring Without Repeating Characters

【题目】

Given a string, find the length of the longest substring without repeating characters.

(给定一个字符串,找字符中的最大非重复子串)

Example 1:

代码语言:javascript
代码运行次数:0
复制
Input: "abcabcbb"
Output: 3 
Explanation: The answer is "abc", with the length of 3. 

Example 2:

代码语言:javascript
代码运行次数:0
复制
Input: "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.

Example 3:

代码语言:javascript
代码运行次数:0
复制
Input: "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3. 
             Note that the answer must be a substring, "pwke" is a subsequence and not a substring.

【分析】

首先,这道题目要求是“非重复最长子串”,所以我们应该在第一时间点想到用HashSet容器。

其次,我们用两个指针,一个遍历数组,另一个检测是否有重复的字符。如果发现重复字符,则remove。

最后用Math.max()函数记录最大的长度即可。

Java实现代码如下:

代码语言:javascript
代码运行次数:0
复制
class Solution {
    public int lengthOfLongestSubstring(String s) {
        int res = 0;
        if (s == null || s.length() == 0) return res; 
        //注意区别字符串的length()方法与数组的length属性
        HashSet<Character> set = new HashSet<>();
        for (int i = 0, j = 0; i < s.length();) {
            if (set.contains(s.charAt(i))) {
                set.remove(s.charAt(j++));
            } else {
                set.add(s.charAt(i++));
                res = Math.max(res, set.size());
            }
        }
        return res;
    }
}
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2018年11月09日,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • Longest Substring Without Repeating Characters
  • 【题目】
  • 【分析】
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档