算法-字符串-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;}
}