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

一、思路： 

        无重复针对唯一的元素首选哈希表方法

        在字符串中找出最长字串——动态数组

二、使用的一些常见方法

        1.HashMap

        a.声明

HashMap<Character,Integer> map=new HashMap();

        b.添加元素

map.put(s.charAt(i),i);

         c.查询是否有对应的元素存在并获取

map.get(s.charAt(i));

        d.是否有对应的元素存在

map.containsKey(s.charAt(i));

 三、核心逻辑

      遍历该字符串

        判断当前字符是否已经存在于map中

                情况一：不存在，放入map中，并将当前记录该最长子串的长度dp[i]=dp[i-1]+1

if(!map.contaionsKey(s.charAt(i))){
    map.put(s.charAt(i),i);//添加当前元素
    dp[i]=dp[i-1]+1;//记录当前位置的最长子串长度
}

                情况二：存在，查询到map中对应元素的value,并存储在变量left中（即s中的数组下标），此时dp[i]为：               

   dp[i]=Math.min(dp[i-1]+1,left-i);

阐释：left-i："aba",i为第一个“a”的数组下标，即i=0；

                               left为第二个“a”的数组下标，即left=2

        那么此时该字符串的子串长度为i-left=2

        dp[i-1]+1:其目的是为了防止“abba”的情况

                        如果dp[i]=i-left的逻辑，那么此时该字符串的子串长度为left-i=3，即“bba”，但实际上应该是2，即“ba”，所以应该还要考虑到dp[i-1]的子串情况

四、代码实现

class Solution {
    public int lengthOfLongestSubstring(String s) {
        Map<Character, Integer> set = new HashMap<>();
        int[] dp = new int[s.length()];
        int res = 0;
        int left = 0;
        for (int i = 0; i < s.length(); i++) {
            if (i == 0) {
                dp[0] = 1;
                set.put(s.charAt(0), 0);
            } else {
                if (!set.containsKey(s.charAt(i))) {
                    set.put(s.charAt(i), i);
                    dp[i] = dp[i - 1] + 1;
                } else {
                    left = set.get(s.charAt(i));
                    dp[i] = Math.min(dp[i - 1] + 1, i - left);
                   
                    set.put(s.charAt(i), i);
                }
            }
            res = Math.max(res, dp[i]);
        }
        return res;
    }
}

原文地址：https://blog.csdn.net/2301_76799207/article/details/144077370

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！