首页 > 代码库 > Minimum Window Substring &&& Longest Substring Without Repeating Characters 快慢指针,都不会退,用hashmap或者其他结构保证
Minimum Window Substring &&& Longest Substring Without Repeating Characters 快慢指针,都不会退,用hashmap或者其他结构保证
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 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。