找到字符串中的异位词

public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param s string字符串 
     * @param p string字符串 
     * @return int整型vector
     */
//直接取s中长度和p相等的子串，然后sort一下看是否相等即可
    vector<int> findWord(string s, string p) {
        vector<int>res;
        int l1 = s.size();
        int l2 = p.size();
        sort(p.begin(),p.end());
        for(int i=0;i<=l1-l2;i++){
            string temp = s.substr(i,l2);
            sort(temp.begin(),temp.end());
            if(temp==p){
                res.push_back(i);
            }
        }
        return res;
    }
};

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param s string字符串 
     * @param p string字符串 
     * @return int整型vector
     */
    vector<int> findWord(string s, string p) {
        // write code here
        int hs[26]={0};
        int hp[26]={0};
        vector<int> res;
        for( auto ch:p){
            hp[ch-'a']++;
        }
        for(int left =0,right=0;right<s.size();right++){
            hs[s[right]-'a']++;
            while(hs[s[right]-'a']>hp[s[right]-'a']){
                hs[s[left]-'a']--;
                left++;
            }
            if(right -left+1==p.size()){
                res.push_back(left);
            }
        }
        return res;
        
    }
};

package main

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param s string字符串 
 * @param p string字符串 
 * @return int整型一维数组
*/
func findWord( s string ,  p string ) []int {
    if len(s)<len(p){
        return nil
    }
    cnt1:=map[byte]int{}
    for _,ch:=range []byte(p){
        cnt1[ch]++
    }
    cnt2:=map[byte]int{}
    ans:=[]int{}
    for _,ch:=range []byte(s[:len(p)]){
        cnt2[ch]++
    }
    if check(cnt2,cnt1){
        ans=append(ans,0)
    }
    for l,r:=0,len(p);r<len(s);l,r=l+1,r+1{
        cnt2[s[r]]++
        if cnt2[s[l]]==1{
            delete(cnt2,s[l])
        }else{
            cnt2[s[l]]--
        }
        if check(cnt2,cnt1){
            ans=append(ans,l+1)
        }
    }
    return ans
}

func check(cnt2,cnt1 map[byte]int)bool{
    for k,v:=range cnt2{
        if _,ok:=cnt1[k];!ok{
            return false
        }
        if v!=cnt1[k]{
            return false
        }
    }
    return true
}

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param s string字符串
 * @param p string字符串
 * @return int整型一维数组
 * @return int* returnSize 返回数组行数
 */
int isCongruent(char* s, char* c) {
    // write code here
    // if (strlen(s) != strlen(c))
    //     return -1;
    int* hash1 = (int*)calloc(26, sizeof(int));
    int* hash2 = (int*)calloc(26, sizeof(int));
    for (int i = 0; i < strlen(c); i++) {
        hash1[s[i] - 'a'] += 1;
        hash2[c[i] - 'a'] += 1;
    }
    //int count = 0;
    for (int j = 0; j < 26; j++) {

        if (hash1[j] != hash2[j])
            return -1;
        // if (hash1[j] != 0)
        //     count += 1;

    }
    return strlen(s);
}
int* findWord(char* s, char* p, int* returnSize ) {
    // write code here
    int s_len = strlen(s);
    int p_len = strlen(p);
    printf("%d %d",s_len,p_len);
    int* ans = (int*)malloc(s_len*10* sizeof(int));
    int count=0;
    for (int i = 0; i + p_len <= s_len; i++) {
        // char *temp=(char *)malloc((p_len+10)*sizeof(char));
        // strncpy(temp,s+i,p_len);
        if(isCongruent(s+i,p)!=-1){
               ans[count++]=i;
        }
    }
    *returnSize=count;
    return ans;
}

public ArrayList<Integer> findWord (String s, String p) {
        // write code here
        int[] arr=new int[26];
        for(char c : p.toCharArray()){
            arr[c-'a']+=1;
        }
        
        int i=0;
        ArrayList<Integer> res=new ArrayList<>();
        for(int j=0;j<s.length();j++){
            char c = s.charAt(j);
            arr[c-'a']-=1;
            while(arr[c-'a']<0 && i>=0 && i<s.length()){
                char pre=s.charAt(i);
                arr[pre-'a']+=1;
                i++;
            }
            if(j-i+1==p.length()){
                res.add(i);
            }
        }
        return res;
    }

# -*- coding: utf-8 -*-


#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param s string字符串
# @param p string字符串
# @return int整型一维数组
#
class Solution:
    """
    题目：
        https://www.nowcoder.com/practice/9ff491c910e5427fab6ae67745929085?tpId=196&tqId=40518&rp=1&ru=/exam/oj&qru=/exam/oj&sourceUrl=%2Fexam%2Foj%3Fpage%3D8%26tab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D196&difficulty=undefined&judgeStatus=undefined&tags=&title=
    算法：
        1. 使用pNums[26]，统计字符串p中每个字符出现次数
        2. 滑动窗口法，窗口大小为[left, right], right - left = len(p)，初始left = 0, right = len(p) - 1, 使用sNums[26]统计窗口内字符出现次数，如果pNums = sNums，将left加入结果res中，移动窗口，知道right = len(s)结束
    复杂度：
        时间复杂度：O(n)
        空间复杂度：O(1)
    """

    def findWord(self, s, p):
        # write code here
        n, m = len(s), len(p)
        pNums, sNums = [0] * 26, [0] * 26

        for i in range(m):
            pNums[ord(p[i]) - ord("a")] += 1
            sNums[ord(s[i]) - ord("a")] += 1

        res = []
        left, right = 0, m - 1
        while right < n:
            if sNums == pNums:
                res.append(left)
            sNums[ord(s[left]) - ord("a")] -= 1
            left += 1
            right += 1
            if right < n:
                sNums[ord(s[right]) - ord("a")] += 1
        return res


if __name__ == "__main__":
    sol = Solution()

    # s, p = "cabac", "abc"

    s, p = "ababab", "ab"

    res = sol.findWord(s, p)

    print res