fd

dingjikerbo · dingjikerbo · commit fcc97aef1a3e · 2018-12-10T19:49:06.000+08:00
diff --git a/leetcode/solution/src/LongestSubstringWithoutRepeatingCharacters.java b/leetcode/solution/src/LongestSubstringWithoutRepeatingCharacters.java
@@ -3,22 +3,17 @@
  */
 public class LongestSubstringWithoutRepeatingCharacters {
 
-    // 耗时39ms，性能挺好
     public int lengthOfLongestSubstring(String s) {
         int[] count = new int[256];
-
-        int maxLen = 0;
-
-        for (int i = 0, j = 0; j < s.length(); ) {
-            if (count[s.charAt(j)] == 0) {
-                count[s.charAt(j)]++;
-                maxLen = Math.max(maxLen, j - i + 1);
-                j++;
-            } else {
-                --count[s.charAt(i++)];
+        int max = 0;
+        for (int i = 0, j = 0; i < s.length(); i++) {
+            char c = s.charAt(i);
+            count[c]++;
+            for ( ; j < i && count[c] > 1; j++) {
+                count[s.charAt(j)]--;
             }
+            max = Math.max(max, i - j + 1);
         }
-
-        return maxLen;
+        return max;
     }
 }
diff --git a/leetcode/src/Main.java b/leetcode/src/Main.java
@@ -1,16 +1,43 @@
 import com.sun.org.apache.xpath.internal.operations.Bool;
 
 import java.util.*;
+import java.util.concurrent.*;
 
 public class Main {
 
     public static class Solution {
+        public int lengthOfLongestSubstring(String s) {
+            HashMap<Character, Integer> map = new HashMap<>();
+            int max = 0;
+            for (int i = 0, j = 0; i < s.length(); i++) {
+                char c = s.charAt(i);
+                map.put(c, map.getOrDefault(c, 0) + 1);
+                for ( ; j < i && map.get(c) > 1; j++) {
+                    char cc = s.charAt(j);
+                    map.put(cc, map.get(cc) - 1);
+                }
+                max = Math.max(max, i - j + 1);
+            }
+            return max;
+        }
 
-        public TreeNode pruneTree(TreeNode root) {
-
+        public int lengthOfLongestSubstring(String s) {
+            int[] count = new int[256];
+            int max = 0;
+            for (int i = 0, j = 0; i < s.length(); i++) {
+                char c = s.charAt(i);
+                count[c]++;
+                for ( ; j < i && count[c] > 1; j++) {
+                    count[s.charAt(j)]--;
+                }
+                max = Math.max(max, i - j + 1);
+            }
+            return max;
         }
+
     }
 
+
     public static void main(String[] args) {
         Solution s = new Solution();
     }
