ADD

leosanqing · leosanqing · commit f1f90e1f359c · 2021-04-06T17:00:16.000+08:00
3 &#25214;&#20986;&#26368;&#38271;&#19981;&#37325;&#22797;&#30340;&#23376;&#20018;
diff --git a/java-note-algorithm/src/main/java/com/leosanqing/leetcode/medium/string/_3_longest_substring_without_repeating_characters.java b/java-note-algorithm/src/main/java/com/leosanqing/leetcode/medium/string/_3_longest_substring_without_repeating_characters.java
@@ -0,0 +1,66 @@
+package com.leosanqing.leetcode.medium.string;
+
+import java.util.HashMap;
+import java.util.Map;
+
+/**
+ * @description: Given a string s, find the length of the longest substring without repeating characters.
+ * <p>
+ * &#32473;&#23450;&#23383;&#31526;&#20018;s&#65292;&#25214;&#21040;&#26368;&#38271;&#23376;&#23383;&#31526;&#20018;&#30340;&#38271;&#24230;&#32780;&#19981;&#37325;&#22797;&#23383;&#31526;&#12290;
+ * <p>
+ * ` Example 1:
+ * <p>
+ * ` Input: s = "abcabcbb"
+ * ` Output: 3
+ * ` Explanation: The answer is "abc", with the length of 3.
+ * ` Example 2:
+ * <p>
+ * ` Input: s = "bbbbb"
+ * ` Output: 1
+ * ` Explanation: The answer is "b", with the length of 1.
+ * ` Example 3:
+ * <p>
+ * ` Input: s = "pwwkew"
+ * ` Output: 3
+ * ` Explanation: The answer is "wke", with the length of 3.
+ * ` Notice that the answer must be a substring, "pwke" is a subsequence and not a substring.
+ * ` Example 4:
+ * <p>
+ * ` Input: s = ""
+ * ` Output: 0
+ * <p>
+ * ` @author: rtliu
+ * ` @date: 2021/4/6 3:41 &#19979;&#21320;
+ */
+public class _3_longest_substring_without_repeating_characters {
+    public static void main(String[] args) {
+        System.out.println(lengthOfLongestSubstring("abba"));
+    }
+
+    /**
+     * &#36825;&#20010;&#26159;&#20856;&#22411;&#30340;&#28369;&#21160;&#31383;&#21475;&#31867;&#30340;&#39064;&#22411;
+     *
+     * &#25105;&#20204;&#36935;&#21040;&#30456;&#21516;&#30340;&#23383;&#31526;&#23601;&#20002;&#24323;&#20043;&#21069;&#23383;&#31526;&#24038;&#36793;&#30340;&#25152;&#26377;&#23383;&#31526;
+     * @param s
+     * @return
+     */
+    public static int lengthOfLongestSubstring(String s) {
+        Map<Character, Integer> map = new HashMap<>(s.length() * 2);
+
+        int result = 0;
+        int head = 0;
+
+        for (int i = 0; i < s.length(); i++) {
+            char c = s.charAt(i);
+
+            if (map.containsKey(c) && head < map.get(c)) {
+                head = map.get(c);
+            }
+            // i+1 &#34920;&#31034;&#24403;&#21069;&#23383;&#31526;&#30340;&#23454;&#38469;&#20301;&#32622;
+            result = Math.max(i + 1 - head, result);
+            map.put(c, i + 1);
+        }
+
+        return result;
+    }
+}
