【力扣】个人理解后整理的解题思路:力扣题库第三题

人语驿边桥 发表于 2020/11/02 07:05:31 2020/11/02
【摘要】 一步步拆解、补充,直到完整解题

题目

给定一个字符串,请你找出其中不含有重复字符的 最长子串 的长度。

解题思路

一步步拆解、补充,直到完整解题


1.首先想到的是需要循环整个字符串

代码

```java

class Solution {

     int lengthOfLongestSubstring(String s) {

        // 循环整个字符串

        int len = s.length();

        for (int i = 0i < leni++) {


        }

        return 0;

    }

}

```


2.整个解题的过程大致是:

1)从最左边的字符开始与右边的字符一一比对,发现有重复的字符之后,计算当前子字符串的长度;

2)移动最左边的字符,重复1)过程,直到字符串的最右边结束,即循环整个字符串。

技巧:

a)在判断字符串重复字符的技巧,使用Set

b)移动过程中右指针始终向右移动,不需要循环,如同一个移动的窗口。

c)字符串循环开始时,需要从Set中移除上一个字符串中的字符

步骤:

1)初始化右指针、无重复子字符串长度、Set容器

2)当右指针未到字符串最后边,并且右指针所指字符不包含在子字符串时,继续循环操作

3) 计算当前子字符串的长度是否大于上次计算的字符串长度

4)从Set中移除上一个字符串中的字符


代码

```java

class Solution {

     int lengthOfLongestSubstring(String s) {

        // 1)初始化右指针

        int rk = 0;

        // 1)初始化无重复子字符串长度

        int subLen = 0;

        // 1)初始化Set容器

        Set<CharactersubSet = new HashSet<>();

        // 循环整个字符串

        int len = s.length();

        for (int i = 0i < leni++) {

            // 4)从Set中移除上一个字符串中的字符

            if (i != 0) {

                subSet.remove(s.charAt(i - 1));

            }

            // 2)当右指针未到字符串最后边,并且右指针所指字符不包含在子字符串时,继续循环操作

            while (rk < len && !subSet.contains(s.charAt(rk))) {

                // 将右指针所指字符放入字符Set中

                subSet.add(s.charAt(rk));

                // 右指针向右移动

                rk = rk + 1;

            }

            // 3) 计算当前子字符串的长度是否大于上次计算的字符串长度

            subLen = Math.max(subLenrk - i);

        }

        return subLen;

    }

}

```

【版权声明】本文为华为云社区用户原创内容,转载时必须标注文章的来源(华为云社区),文章链接,文章作者等基本信息,否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件至:cloudbbs@huaweicloud.com进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容。
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。