最短超串-滑动窗口

class Solution { public int[] shortestSeq(int[] big, int[] small) { //左右双指针表示滑动窗口，start和min用来保存最优解 int left = 0,right = 0,start = 0; int min = Integer.MAX_VALUE; //window用来记录当前窗口包含的字符和出现的次数 //needs用来记录small当中出现的字符和包含的次数 HashMap<Integer,Integer> window = new HashMap<>(); HashMap<Integer,Integer> needs = new HashMap<>(); //记录small中出现的字符和包含的次数 for(Integer c:small ) needs.put(c,needs.getOrDefault(c,0)+1); //match用来保存匹配的个数 int match = 0; //移动right扩大窗口 while(right<big.length){ Integer c1 = big[right]; if(needs.containsKey(c1)){ window.put(c1,window.getOrDefault(c1,0)+1); if(window.get(c1)==needs.get(c1)){ match++; } } right++; //当匹配个数满足small时，移动 left 缩小窗口进行优化 while (match==needs.size()){ //更新最小窗口 if(right-left<min){ start = left; min = right-left; } Integer c2 = big[left]; if(needs.containsKey(c2)){ window.put(c2,window.getOrDefault(c2,0)-1); if(window.get(c2)<needs.get(c2)){ match--; } } left++; } } return min == Integer.MAX_VALUE? new int[0]:new int[]{start,min+start-1}; } }

以上代码是参考以为大佬的，可以说是非常详细了，下面的是在笔试中写的，用例测试通过率居然为0，（估计是凉了）

public class minSubstring { public int minLength(String str1, String str2){ if(str1 == null || str2 ==null || str1.length() < str2.length()){ return 0; } char[] chas1 = str1.toCharArray(); char[] chas2 = str2.toCharArray(); int[] map = new int[256]; for (int i=0; i< chas2.length; i++){ map[chas2[i]]++; } int left= 0; int right = 0; int minLen =Integer.MAX_VALUE; int match =chas2.length; while (right != chas1.length){ map[chas1[right]]--; if(map[chas1[right]] >= 0){ match--; } if(match == 0){ while (map[chas1[left]] < 0){ map[chas1[left++]]++; } minLen = Math.min(minLen, right - left + 1); match++; map[chas1[left++]]++; } right++; } return minLen == Integer.MAX_VALUE ? 0 :minLen; } public static void main(String[] args){ minSubstring tmp = new minSubstring(); String str1 = "abcde"; String str2 = "ac"; System.out.println(tmp.minLength(str1, str2)); String str3 = "12345"; String str4 = "344"; System.out.println(tmp.minLength(str3, str4)); } }