美文网首页
LeetCode 最长无重复字符的子串

LeetCode 最长无重复字符的子串

作者: MarioBai | 来源:发表于2019-01-08 14:19 被阅读0次

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

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

解题思路
使用滑动窗口的思想来解决这个问题,窗口的边界可以理解为下标,i表示字符串的左边界,j表示字符串的右边界。假设在数组(i,j)的范围内发现str[i]=str[j]。那么只需要将i的值赋值为j+1即可。然后再进行以上的判断。这里我们利用HashMap。

import java.util.HashMap;

/*
 * @author: mario
 * @date: 2019/1/5
 * 无重复字符的最长子串
 * **/
public class Problem03 {
    public int lengthOfLongestSubstring(String str) {
        if(str.length() == 0 || str == null){
            return 0;
        }
        int len = str.length(), ans = 0;
        HashMap<Character, Integer> map = new HashMap<>();
        for(int j = 0, i = 0; j < len; j++){
            if(map.containsKey(str.charAt(j))){
                i = Math.max(map.get(str.charAt(j)), i);
            }
            ans = Math.max(ans, j - i + 1);
            map.put(str.charAt(j), j+1); 
        }
        return ans;
    }
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Problem03 pb = new Problem03();
        String str = "abcabcbb";
        int result = pb.lengthOfLongestSubstring(str);
        System.out.println("result:"+result);
    }

}

LeetCode题目地址: https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/

相关文章

网友评论

      本文标题:LeetCode 最长无重复字符的子串

      本文链接:https://www.haomeiwen.com/subject/ahgvrqtx.html