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

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

作者头像
yesr
发布2019-03-14 13:02:42
2900
发布2019-03-14 13:02:42
举报

Longest Substring Without Repeating Characters

【题目】

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

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

Example 1:

Input: "abcabcbb"
Output: 3 
Explanation: The answer is "abc", with the length of 3. 

Example 2:

Input: "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.

Example 3:

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实现代码如下:

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
  • 【题目】
  • 【分析】
相关产品与服务
容器服务
腾讯云容器服务(Tencent Kubernetes Engine, TKE)基于原生 kubernetes 提供以容器为核心的、高度可扩展的高性能容器管理服务,覆盖 Serverless、边缘计算、分布式云等多种业务部署场景,业内首创单个集群兼容多种计算节点的容器资源管理模式。同时产品作为云原生 Finops 领先布道者,主导开源项目Crane,全面助力客户实现资源优化、成本控制。
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档