2021-06-30：给定长度为m的字符串aim，以及一个长度为n的字符串str ，问能否在str中找到一个长度为m的连续子串，

福大大架构师每日一题

发布于 2021-08-05 08:14:23

1K00

代码可运行

文章被收录于专栏：福大大架构师每日一题福大大架构师每日一题

运行总次数：0

代码可运行

2021-06-30：给定长度为m的字符串aim，以及一个长度为n的字符串str ，问能否在str中找到一个长度为m的连续子串，使得这个子串刚好由aim的m个字符组成，顺序无所谓，返回任意满足条件的一个子串的起始位置，未找到返回-1。

福大大答案2021-06-30：

map+all+滑动窗口。

map：欠账表。

all：总欠账数。

代码用golang编写。代码如下：

package main

import "fmt"

func main() {
    s1 := "moonfdd"
    s2 := "ddf"
    ret := containExactly3(s1, s2)
    fmt.Println(ret)
}

func containExactly3(s1 string, s2 string) int {
    if len(s1) < len(s2) {
        return -1
    }
    M := len(s2)
    count := make([]int, 256)
    for i := 0; i < M; i++ {
        count[s2[i]]++
    }
    all := M
    R := 0
    // 0~M-1
    for ; R < M; R++ { // 最早的M个字符，让其窗口初步形成
        if count[s1[R]] > 0 {
            count[s1[R]]--
            all--
        } else {
            count[s1[R]]--
        }
    }
    // 窗口初步形成了，并没有判断有效无效，决定下一个位置一上来判断
    // 接下来的过程，窗口右进一个，左吐一个
    for ; R < len(s1); R++ {
        if all == 0 { // R-1
            return R - M
        }
        if count[s1[R]] > 0 {
            all--
            count[s1[R]]--
        } else {
            count[s1[R]]--
        }
        if count[s1[R-M]] >= 0 {
            count[s1[R-M]]++
            all++
        } else {
            count[s1[R-M]]++
        }
    }
    if all == 0 {
        return R - M
    } else {
        return -1
    }
}