Skip to main content

3. 无重复字符的最长子串

URL 3. 无重复字符的最长子串

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

 

内容如下

示例 1:

输入: s = "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。注意 "bca" 和 "cab" 也是正确答案。

示例 2:

输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

示例 3:

输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
     请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

 

提示：

  • 0 <= s.length <= 5 * 104
  • s 由英文字母、数字、符号和空格组成

解题思路

String 的本质就是 char[], 例如:上面就是

97,98,99,97,98,99,98,98
final length:3
98,98,98,98,98
final length:1
112,119,119,107,101,119
final length:3
112,119,32,107,101,49,49,49,119,32,32,32,32
final length:6

所以本质就是

  1. 拿到不重复的char的值,放到list中
  2. 及时用list.size()来更新 maxLenth
  3. 遇到重复值时重新开始计算

自己写的

package demo.Solution3;

import lombok.extern.slf4j.Slf4j;

import java.util.*;

@Slf4j
public class Test3 {

    public static void main(String[] args) {
        String s = "abcabcbb";
        calcLongestStringLength(s);
        s = "bbbbb";
        calcLongestStringLength(s);
        s = "pwwkew";
        calcLongestStringLength(s);
        s = "pw ke111w    ";
        calcLongestStringLength(s);
    }

    private static void calcLongestStringLength(String s) {
        // 使用双指针进行选中和更新
        int left = 0;
        int right = 0;
        int maxLen = 0;
        char[] chars = s.toCharArray();
        printStringCharArray(s);
        // 输出char[]
        List<Character> list = new ArrayList<>();
        List<Character> maxList = new ArrayList<>();
        list.add(chars[right]);
        for (int i = 0; i < chars.length; i++) {

            char next = chars[right++];
            // 用左指针去获取数据
            if (list.contains(next)) {
                maxLen = Math.max(maxLen, list.size());
                if (maxLen > maxList.size()) {
                    maxList = list;
                }
                list.clear();
                // 重新来呗
            }
                list.add(next);
        }
        //System.out.println("max list :" + maxList.toString());
        System.out.println("final length:" + maxLen);
    }

    private static void printStringCharArray(String s) {
        // 字符串的每一个字符都是char[]
        char[] sChars = s.toCharArray();
        List<String> list = new ArrayList<>();
        for (char c : sChars) {
            int value = c;
            list.add(String.valueOf(value));
        }
        String result = String.join(",", list);
        System.out.println(result);
    }


}
Back to top