这个题用集合类去实现的时候踩了好几个坑containsAll()方法是元素维度跟个数无关{a,b}contailsAll{a,b,b}居然返回trueremove方法指定元素类型删除一次只删除一个元素。比如{a,b,b}执行一次remove(new Character(b))以后剩下{a,b}而不是把b全删了remove这里还有个坑删除b的时候你不能remove(b)这样写因为底层会发生类型转换char类型给你变成int类型变成了删除第int个元素。。法一滑动窗口维护s1长度大小的滑动窗口在s2身上滑动每次步长为1。对于每个滑动窗口内部维护一个把s1每个字符都放进去的list集合遍历一个元素就remove一个如果窗口遍历完list集合为空就说明匹配成功了。class Solution { public boolean checkInclusion(String s1, String s2) { ListCharacter list1 new ArrayList(); //答案 boolean ansfalse; //子串入list for(int i0; is1.length();i){ list1.add(s1.charAt(i)); } //主串窗口方式遍历步长1 for(int i0;is2.length()-s1.length();i){ ListCharacter temp new ArrayList(list1); //浅拷贝 for(int offset0;offsets1.length();offset){ //注意1remove(b)这样写的话底层会发生数据类型转换b给你转成int变成remove第int个元素 //所以必须用包装类 //注意2list指定元素的remove只会移除一个比如{a,b,b}移除一次b只会删除一个b不会都删了 temp.remove(new Character(s2.charAt(ioffset))); } if (temp.size()0){ anstrue; break; } } return ans; } }时间复杂度O(m×n)m和n分别是主串和子串的长度空间复杂度O(n)n是子串的长度会超时。想出来法一就可以了官方给的法二有问题法二优化滑动窗口 有问题法一相当于暴力搜索优化暴力搜索的思路就是想一想下一轮是否能利用上一轮的信息。观察滑动窗口的滑动方式就能发现下一轮其实就是把上一轮的第一个元素给剔除再引入一个新元素罢了中间c c d a是不变的也就是可以重复利用的。这样时间复杂度就可以变成大概O(mn)。不能在上一版本的代码上改了因为上一轮的版本不能计数remove操作如果删掉了两个是无感的。要找一个容器来计数首先想到hashmap但是判断匹配的时候判断标准就得是所有key的value都得是0这样又要遍历hashmap官方题解是存在数组里利用了数组的Arrays.equals方法其实这样时间复杂度也是O(m×n)只不过没把Arrays.equals的时间复杂度算进来罢了。class Solution { public boolean checkInclusion(String s1, String s2) { if(s1.length()s2.length()) return false; int[] nums1 new int[26]; int[] nums2 new int[26]; //s1作为用于比较的参考 for(int i0;is1.length();i){ nums1[s1.charAt(i)-a]; } //第一个窗口需要单独处理 for(int i0;is1.length();i){ nums2[s2.charAt(i)-a]; } if(Arrays.equals(nums1,nums2)) return true; //主串滑动窗口步长为1 for(int i1;is2.length()-s1.length();i){ //进入新一轮最前面的一个元素退出 nums2[s2.charAt(i-1)-a]--; //进入窗口一个新元素 nums2[s2.charAt(is1.length()-1)-a]; if(Arrays.equals(nums1,nums2)) return true; } return false; } }
这个题用集合类去实现的时候踩了好几个坑containsAll()方法是元素维度跟个数无关{a,b}contailsAll{a,b,b}居然返回trueremove方法指定元素类型删除一次只删除一个元素。比如{a,b,b}执行一次remove(new Character(b))以后剩下{a,b}而不是把b全删了remove这里还有个坑删除b的时候你不能remove(b)这样写因为底层会发生类型转换char类型给你变成int类型变成了删除第int个元素。。法一滑动窗口维护s1长度大小的滑动窗口在s2身上滑动每次步长为1。对于每个滑动窗口内部维护一个把s1每个字符都放进去的list集合遍历一个元素就remove一个如果窗口遍历完list集合为空就说明匹配成功了。class Solution { public boolean checkInclusion(String s1, String s2) { ListCharacter list1 new ArrayList(); //答案 boolean ansfalse; //子串入list for(int i0; is1.length();i){ list1.add(s1.charAt(i)); } //主串窗口方式遍历步长1 for(int i0;is2.length()-s1.length();i){ ListCharacter temp new ArrayList(list1); //浅拷贝 for(int offset0;offsets1.length();offset){ //注意1remove(b)这样写的话底层会发生数据类型转换b给你转成int变成remove第int个元素 //所以必须用包装类 //注意2list指定元素的remove只会移除一个比如{a,b,b}移除一次b只会删除一个b不会都删了 temp.remove(new Character(s2.charAt(ioffset))); } if (temp.size()0){ anstrue; break; } } return ans; } }时间复杂度O(m×n)m和n分别是主串和子串的长度空间复杂度O(n)n是子串的长度会超时。想出来法一就可以了官方给的法二有问题法二优化滑动窗口 有问题法一相当于暴力搜索优化暴力搜索的思路就是想一想下一轮是否能利用上一轮的信息。观察滑动窗口的滑动方式就能发现下一轮其实就是把上一轮的第一个元素给剔除再引入一个新元素罢了中间c c d a是不变的也就是可以重复利用的。这样时间复杂度就可以变成大概O(mn)。不能在上一版本的代码上改了因为上一轮的版本不能计数remove操作如果删掉了两个是无感的。要找一个容器来计数首先想到hashmap但是判断匹配的时候判断标准就得是所有key的value都得是0这样又要遍历hashmap官方题解是存在数组里利用了数组的Arrays.equals方法其实这样时间复杂度也是O(m×n)只不过没把Arrays.equals的时间复杂度算进来罢了。class Solution { public boolean checkInclusion(String s1, String s2) { if(s1.length()s2.length()) return false; int[] nums1 new int[26]; int[] nums2 new int[26]; //s1作为用于比较的参考 for(int i0;is1.length();i){ nums1[s1.charAt(i)-a]; } //第一个窗口需要单独处理 for(int i0;is1.length();i){ nums2[s2.charAt(i)-a]; } if(Arrays.equals(nums1,nums2)) return true; //主串滑动窗口步长为1 for(int i1;is2.length()-s1.length();i){ //进入新一轮最前面的一个元素退出 nums2[s2.charAt(i-1)-a]--; //进入窗口一个新元素 nums2[s2.charAt(is1.length()-1)-a]; if(Arrays.equals(nums1,nums2)) return true; } return false; } }
