【算法题目】字符串排列

leetcode567题

m最大是26感觉可以用位运算，每次判断就2个整数比较一下，性能应该会好一点

直接O(n),我理解判断长度就可以，不需要再比较子串了 import java.util.*; public class Main {     public static void main(String[] args) {         Character[] arr = new Character[]{'a&(417)#39;,'b&#39;,'c&(2248)#39;,'d&#39;};         LinkedList<Character> word = new LinkedList<>(Arrays.asList(arr));         String s = "tbcacbdata";         LinkedList<Character> window = new LinkedList<>();         int index =1;         for(char c: s.toCharArray()){             // 如果是word中出现的字母             if(word.contains(c)){                 // 首先移动windows到重复字母之后                 if(window.contains(c)){                     while (window.pollFirst() != c);                 }                 window.add(c);                 // 判断是否存在答案                 if(window.size()==word.size()){                     System.out.println(index-word.size());                     return;                 }             }             // 不是 word中的字母             else {                 window.clear();             }             index++;         }     } }

哈哈哈华为一面的时候遇到了这道题，我记得有个数学理论，可以用O(n)的时间复杂度解决出来。然后面试官问我的算法优点是啥，我说快吧，他问我缺点，我摇摇头，他说缺点是很难看懂，不过的确可以做出来。

package timu; /**  * @program: test-lrg  * @description: 编程题目  * @author: Arell  * @create: 2019-12-24 09:09  **/ public class Demo01 {     public static void main(String[] args) {         /*作者：Mono_Chrome         链接：https://www.nowcoder.com/discuss/357566         来源：牛客网         给定m个不重复的字符 [a, b, c, d]，以及一个长度为n的字符串tbcacbdata，问能否在这个字符串中找到一个长度为m的连续子串，         使得这个子串刚好由上面m个字符组成，顺序无所谓，返回任意满足条件的一个子串的起始位置，未找到返回-1。比如上面这个例子，acbd，3。         这道题是leetcode原题吗？求解题思路*/         //Scanner scanner = new Scanner(System.in);         char[] chars = {'a', 'b', 'c', 'd'};         String s = "gsjkdgabdc";         int m = chars.length;         int n = s.length();         //将字符拼接字符串         StringBuilder charStr = new StringBuilder();         for (int i = 0; i < chars.length; i++) {             charStr.append(chars[i]);         }         //遍历字符串,判断         String[] strArr = s.split("");         int index = 0;         for (int i = 0; i < strArr.length; i++) {             boolean flag = true;             if (charStr.toString().contains(strArr[i]) && i + m <= n ) {                 String temp = s.substring(i, i + m);                 for (char aChar : chars) {                     if (!temp.contains(aChar + "")) {                         //只要有不包含的,就false                         flag = false;                     }                 }             }else {                 flag = false;             }             if (flag) {                 //找到了第一个满足条件的,返回并return                 index = i;                 System.out.println(index);                 return;             } else {                 index = -1;             }         }         System.out.println(index);     } }

#include<stdio.h> using namespace std;   int main(){ char s[]={'t','b','c','a','c','b','d','a','t','a'}; char t[]={'a','b','c','d'}; int s_len=10,t_len=4; int res; if(s_len<t_len){ res=-1; printf("%d",res); return 0; } //申请一个散列表，记录窗口中元素的情况  int hash[26]={0}; for(int i=0;i<t_len;++i){ ++hash[t[i]-'a']; } int l=0,count=0; for(int r=0;r<s_len;++r){ --hash[s[r]-'a']; if(hash[s[r]-'a']>=0){ //s[r]处的字符在t中  ++count; } //向右移动左指针           if(r>t_len-1) {              ++hash[s[l]-'a'];              if (hash[s[l]-'a']>0) --count;              ++l;          }          if(count==t_len && r-l+1==t_len){ res=l; printf("%d",res); return 0; } } res=-1;//没有找到 printf("%d",res); return 0; } 

leetcode原题吧。set+双指针。set保存m。windows保存双指针l，r区间的元素。当n[r] not in set时，l和r同时加1，当r-l=等于m时，判断是windows和set否相等

利用滑动窗口，同时使用Map存储当前窗口的字符串的所有字符的出现次数，题意说了，m个字符互不相同，因此，符合条件的字符串的长度和Map的size是一致的，可以在窗口滑动中把所有符合的字符串保存起来，这样的时间复杂度是O(n),不过最后需要对满足条件的字符串逐一和目标字符串进行比较

滑动窗口？

遍历符合长度的字串，然后先判断子串有没有重复字符，如果没有则看字串有没有字符不在m里，如果都在则输出

滑动窗口时动态维护m个字符出线的次数如果次数之和等于m就找到了？这种做法不是o(n)的嘛，还需要优化么？

遍历时比较四个字母的和是否相等？是不是能多筛去一些😂

只能想到mn的

感谢各位大佬的回答

最长子字符串衍生题 附带rust实现

滑动窗口+Hash吧， O(n) 的复杂度，比较时只需要对比两个串hash之后的值。     public static int find(String father, String child){         int len1 = father.length();         int len2 = child.length();         if(len1<len2 || len1<=0){             return -1;         }         // 初始化2的N次方         int[] N2 = new int[26];         for(int i=0; i<26; i++){             N2[i] = (int) Math.pow(2,i);         }         // 计算child的值         int childValue = 0;         for(int i=0; i<len2; i++){             childValue += N2[child.charAt(i)-'a&(417)#39;];         }         // System.out.println("childValue---"+ childValue);         int fatherValue = 0;         for(int i=0; i<len1; i++){             if(i>=len2){                 fatherValue -= N2[father.charAt(i-len2)-'a&(417)#39;];             }             fatherValue += N2[father.charAt(i)-'a&(417)#39;];             if(fatherValue == childValue){                 return i-len2+1;             }         }         return -1;     }

用两个hashset就可以吧，复杂度O(n)

用HashMap记录滑动窗口大小为m的字符及数量，同时记录字符种类，有效字符总数（有效字符指不重复的字符数组），维护这些数据 当字符种类数为m时，且有效字符总数为m，返回起始索引

通过hash保证滑动窗口内无重复情况下异或？i~i + m - 1的结果为res，然后下个窗口的异或值直接就是res ^ str[i]^str[ i+m]，也就少了m个元素的hash表遍历

package com.wt.algorithm; import java.util.ArrayList; import java.util.Arrays; import java.util.List; public class Algorithm1 { public static void main(String[] args) { List<Character> a = new ArrayList<>(); a.add('a&(417)#39;); a.add('b&(1071)#39;); a.add('c&(2248)#39;); a.add('d&(406)#39;); String s = "fdsfdscabderfdsabcd"; getIndex(a, s); } private static void getIndex(List<Character> a, String s) { aa : for (int i = 0; i < s.length()-a.size()+1; i++) { char charAt = s.charAt(i); //如果在给定字符中todo比较第二位是否在剩余数组中 if(a.contains(charAt)) { List<Character> b = new ArrayList<>(a); for(int j = 1;j<a.size();j++) { char charAt2 = s.charAt(i+j-1); b.remove(b.indexOf(charAt2)); if(!b.contains(s.charAt(i+j))) break; if(b.size()==1&&b.contains(s.charAt(i+j))) { System.out.println("当前位置开头====="+i); break aa; } } } } } }