首页 > 代码库 > Minimum Window Substring &&& Longest Substring Without Repeating Characters 快慢指针，都不会退，用hashmap或者其他结构保证

Minimum Window Substring &&& Longest Substring Without Repeating Characters 快慢指针，都不会退，用hashmap或者其他结构保证

2024-07-14 12:08:35   222人阅读


 1 

public class Solution { 2     public static int lengthOfLongestSubstring(String s) { 3   4     char[] arr = s.toCharArray(); 5     int pre = 0; 6   7     HashMap<Character, Integer> map = new HashMap<Character, Integer>(); 8   9     for (int i = 0; i < arr.length; i++) {10         if (!map.containsKey(arr[i])) {11             map.put(arr[i], i);12         } else {13             pre = pre > map.size() ? pre : map.size();14             i = map.get(arr[i]);15             map.clear();16         }17     }18  19     return Math.max(pre, map.size());20 }21 }

 

 1 public class Solution { 2     public String minWindow(String S, String T) { 3         char s[]=S.toCharArray(); 4         if(S=="")return ""; 5         int beg=0; 6         int end=0; 7         int d[]=new  int[128]; 8         int size=0; 9         for(int i=0;i<T.length();i++)10         {11             if(d[t[i]]==0) size++;12             d[t[i]]++;13         }14         int d2[]=new int[128];15         int s1=0;16         boolean flag=false;17         18         while(end<s.length)19         {20             if(d[s[end]]==0) {end++;continue;}21              d2[s[end]]++; 22              if(d2[s[end]]==d[s[end]]) s1++;23              end++;24              if(s1==size)25              {26                  while(d2[s[beg]]>d[s[beg]]||d[s[beg]]==0) {d2[s[beg]]--;beg++;}27                  flag=true;28                  break;29              }30            31             32         }33        if(!flag) return "";34         int aend=end-1;35         int abeg=beg;36         int amin=end-beg;37         38     39          while(end<s.length)40          {41              if(d[s[end]]==0){end++;continue;}42              d2[s[end]]++;43             44             while((d2[s[beg]]>d[s[beg]])||d[s[beg]]==0) { 45                 d2[s[beg]]--;beg++;46                 if(end-beg+1<amin)47                 {amin=end-beg+1;48                 aend=end;49                 abeg=beg;50             51                 }52             53                 54                 55                 56             }57             end++;58              59          }60         61             62         63         // 64         return S.substring(abeg,aend+1);65         66         67         68         69         70         71       72         73     }74 }
View Code

 


联系
我们