3.无重复字符的最长字符串.java 中等

问题描述

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

示例 1:

输入: "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

示例 2:

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

示例 3:

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-substring-without-repeating-characters
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
           

解法一：暴力

枚举所以子字符串

利用Set判断子字符串是否重复

Set继承于Collection接口，是一个不允许出现重复元素，并且无序的集合，主要有HashSet和TreeSet两大实现类。

在判断重复元素的时候，Set集合会调用hashCode()和equal()方法来实现。

HashSet是哈希表结构，主要利用HashMap的key来存储元素，计算插入元素的hashCode来获取元素在集合中的位置；

TreeSet是红黑树结构，每一个元素都是树中的一个节点，插入的元素都会进行排序；

参见详解
https://www.jianshu.com/p/d6cff3517688
           

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int n = s.length();
        int ans =0;
        for (int i = 0; i < n; i++){
            for (int j = i + 1; i < n; i++){
                if (allUnique(s,i,j)){
                    ans = Math.max(ans,j-i);
                }
            }
        }
        return ans;
    }
    public boolean allUnique(String s,int start,int end){
        Set<Character> set = new HashSet<>();
        for (int i = start; i < end; i++){
            Character ch = s.charAt(i);
            if (set.contains(ch)){
                return false;
            }
            set.add(ch);
        }
        return true;
    }
}
           

2.解法二

利用滑动窗口

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int n = s.length();
        Set<Character> set = new HashSet<>();
        int ans=0,i=0,j=0;
        while(i<n && j<n){
            if(!set.contains(s.charAt(j))){
                set.add(s.charAt(j++));
                ans = Math.max(ans,j-i);
            }
            else{
                set.remove(s.charAt(i++));
            }
        }
        return ans;
    }
}
           

3.解法三

滑动窗口优化

建立map，键值为元素，值为位置+1（方便i跳到相同元素的下一个位置）

若map中有相同元素，则i直接跳到这个元素的下一个位置，

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int n = s.length(), ans = 0;
        Map<Character,Integer> map = new HashMap<>();
        for (int i=0,j=0;j<n;j++){
            if(map.containsKey(s.charAt(j))){
                i = Math.max(map.get(s.charAt(j)),i);
            }
            map.put(s.charAt(j),j+1);
            ans = Math.max(ans,j-i+1);
        }
        return ans;
    }
}