1.约束性的连续子串问题

约束性的连续子串问题是这样一类问题：满足某种【约束条件】的【连续子串】是问题的解

例如，对于一个由数字组成的字符串'1834620435'，约束这个连续子串的条件可以是子串中奇数个数大于偶数个数，求满足这种约束的子串有几个；又或者是连续子串必须满足和为k，求满足这种约束的子串有几个

2.约束性的连续子串问题分类

一般分为2类

• 计数类。即，求所有满足约束的连续子串有多少个
• 最值类。即，求所有满足约束的连续子串中，最长的那个
  最值类的解决方式可以由计数类的解法强化得到

3.解法模板

3.1计数类约束性的连续子串问题

以leetcode560为例，对模板进行说明

给定一个整数数组nums和一个整数 k，你需要找到该数组中和为 k 的连续的子数组的个数

分析：
1.首先，这是一个【计数类】的约束性的连续子串问题
2.先看最暴力的思路，利用双指针，对所有可能的连续子数组进行遍历，看和是否为k，遍历需要O(n^2)，还需要 O(n) 的时间复杂度遍历子数组来求和，复杂度达到 O(n^3)。那么求和能不能降低复杂度？可以。正是因为问题求的是连续子串。比如，假设我知道nums[0:i]的和，又知道nums[0:j]的和（i<j），那么nums[i:j]的和也就等于两者的差值 = nums[0:j]_sum - nums[0:i]_sum。

两个【同一起点不同终点】的子串做差，就可以得到中间的子串，就是这么一个简单的道理

根据这个思路，我们维护一个pre数组，pre[i]表示从nums[0]到nums[i]的和。这样，通过pre数组就可以求得所有连续子数组的和了
&&
同时，因为本题是计数问题，我们维护一个hash table，记录和为s已经在pre数组中出现了多少个，写作{s: n}

这样一来，当我们计算得到当前和pre[i]，接着通过hash table发现pre[i] - k已经出现了n个，说明从当前下标i往前有连续的子数组的和为k且有n个这样不同的子数组，因此res += n；然后把pre[i]登记入hash table

class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:
        # 模板：pre + hash

        # 初始化pre为[0]，[0]为原始状态，在开始统计nums前存在
        pre = [0]
        # hash table d, 0已经在pre中出现了一次
        d = {0:1}

        res = 0
        for i in range(len(nums)):
            cur_sum = pre[-1] + nums[i]
            pre.append(cur_sum)
            if cur_sum - k in d:
                res += d[cur_sum - k]
            if cur_sum in d:
                d[cur_sum] += 1
            else:
                d[cur_sum] = 1
        return res

从本题可以发现，所有满足题意的连续子数组，实际上都是通过pre[i] - k判断并求出来的。换句话说，这些求出来的连续子数组，都是两个连续子数组的差。例如，nums = [1,2,1,3,0]，k = 3，满足题意的子数组为[1,2], [2,1], [3], [3,0]，其实分别等于[1,2] - [], [1,2,1] - [1], [1,2,1,3] - [1,2,1], [1,2,1,3,0] - [1,2,1]

计数类代码模板（核心）

pre+hash+求余

1.维护一个pre数组，记录前缀状态pre_status。初始化为[0]，[0]为原始状态，在开始统计array元素前存在
2.维护一个hash table，记录在pre中已有状态出现过的次数。初始化为{0:1}，表示前缀状态0已经在pre中出现了一次
3.求余状态已出现次数。假设【当前状态cur_status】与【之前某个状态some pre_status】的差值等于约束条件，那么称这个pre_status为当前状态cur_status的余状态。显然，余状态出现了几次，就有几个满足条件的连续子数组

class Solution:
    def func(self, array, k):
        # 模板：pre + hash

        # 初始化pre为[0]，[0]为原始状态，在开始统计nums前存在
        pre = [0]
        # hash table d, 0已经在pre中出现了一次
        d = {0:1}

        res = 0
        for i in range(len(array)):
            get cur_status 
            pre.append(cur_status)
            # 通过hash table求余状态已出现的次数
            if cur_status - k in d:
                res += d[cur_status - k]
            # 登记当前状态
            if cur_status in d:
                d[cur_status] += 1
            else:
                d[cur_status] = 1
        return res

来个题练手
leetcode1248

给你一个整数数组 nums 和一个整数 k。
如果某个 连续 子数组中恰好有 k 个奇数数字，我们就认为这个子数组是「优美子数组」。请返回这个数组中「优美子数组」的数目

分析：
关键词，连续子数组，约束条件包含k个奇数，求数目，说明是计数型约束性的连续子串问题。直接套模板，pre记录前缀奇数个数，hash table记录pre中的每个值出现了几次，然后求余解决

class Solution:
    def numberOfSubarrays(self, nums: List[int], k: int) -> int:
        # 计数型 约束子串问题
        # 模板：pre数组+hash

        pre = [0]
        hash_table = {0:1}

        res = 0
        for i in range(len(nums)):
            cur_count = nums[i] % 2 + pre[-1]
            pre.append(cur_count)
            if cur_count - k in hash_table:
                res += hash_table[cur_count-k]
            if cur_count in hash_table:
                hash_table[cur_count] += 1
            else:
                hash_table[cur_count] = 1
        return res

3.2最值类约束性的连续子串问题

一般是求满足某种约束条件的最长连续子串的长度

同样的，满足条件的连续子串仍然通过两个同起点异终点的连续子数组做差得到。那么，要使这样的子串最长，做差的两个子串的终点相距就要越远。基于这样的考虑，hash table不再记录每个状态在pre中已经出现的次数，而是记录每个状态在pre中最早出现的下标，以标记目标子串的最前起点位置；同时，在pre数组填充完毕后，逆序遍历（因为目标子串的终点越后越好）求余状态的最早下标，遍历到的当前位置与余状态的最早下标之差即为一个可能的最长长度

最值类代码模板（核心）

pre+hash+逆序遍历pre求余

1.维护一个pre数组，记录前缀状态pre_status。初始化为[0]，[0]为原始状态，在开始统计array元素前存在
2.维护一个hash table，记录在pre中已有状态最早出现的下标。初始化为{0:0}，表示状态0最早在pre中的第0个位置出现
3.逆序遍历pre求当前状态到余状态的下标距离。假设【当前状态cur_status】与【之前某个状态some pre_status】的差值等于约束条件，那么称这个pre_status为当前状态cur_status的余状态。通过hash table求余状态在pre的最早下标，pre遍历到的当前位置与余状态的最早下标之差即为一个可能的最长长度

例
leetcode#### 1124. 表现良好的最长时间段
给定一个数组nums，求大于8的数的个数比不大于8的数的个数多的最长连续子数组长度

思路：
把大于8的数记为1，不大于8的数记为-1，就转化为求【和大于0的最长连续子数组的长度】

class Solution:
    def longestWPI(self, hours: List[int]) -> int:
        # 将劳累天数与不劳累天数的差值delta记为状态s

        # 前缀状态数组
        pre = [0]

        # 使用哈希表登记每个差值状态最早出现的index
        status_dict = {}
        # 初始化哈希表
        status_dict[0] = 0

        res = 0
        delta = 0
        # 填充pre数组和hash table
        for i in range(len(hours)):
            if hours[i] > 8:
                delta += 1
            else:
                delta -= 1
            pre.append(delta)
            if delta not in status_dict:
                # 哈希表登记该差值在pre中最早出现的index
                status_dict[delta] = i+1

        all_status_sort = sorted(list(set(pre)))[::-1]

        # 逆序遍历pre数组，求当前位置与余状态最早位置之差
        for j in range(len(pre)-1, -1, -1):
            while pre[j] > all_status_sort[-1]:
                p = all_status_sort.pop()
                res = max(j-status_dict[p], res)

        return res

leetcode#### 1371. 每个元音包含偶数次的最长子字符串
给你一个字符串 s ，请你返回满足以下条件的最长子字符串的长度：每个元音字母，即 'a'，'e'，'i'，'o'，'u' ，在子字符串中都恰好出现了偶数次

思路：
连续子串，约束条件为元音出现偶数次，求最长长度，显然就是最值型约束性连续子串问题

本题的难点在于，存在5个变量，即5个元音字母出现的次数。变量太多了，不方便处理，因为pre数组只能存一个变量的状态，怎么办？变量压缩。事实上，上一题也是存在2个变量，大于8的数的个数和不大于8的数的个数，我们怎么处理的呢？通过做差把2给变量压缩到了一个变量。那么这题怎么把5个变量压缩成一个变量？本题只关注元音出现次数的【奇偶性】而不关心具体的次数，而奇偶性问题很容易想到用0/1代替。于是，我们维护这样一个变量，它是一个5位二进制数，如01010，表示e、o出现了奇数次，a、i、u出现了偶数次，用pre数组记录它。这样模板就能套起来了

class Solution:
    def findTheLongestSubstring(self, s: str) -> int:

        # pre 记录一个5位二进制数的值
        pre = [0]

        # hash table status_list，记录每个状态首次出现的下标
        status_list = {}
        # 状态0在pre中首次出现的下标为0
        status_list[0] = 0

        status = 0
        res = 0
        for i in range(len(s)):
            if s[i] == 'a':
                status ^= 16
            elif s[i] == 'e':
                status ^= 8
            elif s[i] == 'i':
                status ^= 4
            elif s[i] == 'o':
                status ^= 2
            elif s[i] == 'u':
                status ^= 1
            pre.append(status)
            if status not in status_list:
                status_list[status] = i + 1
            else:
                res = max(res, i + 1 -status_list[status])
        return res

4.总结

计数类和最值类
相同点是，都靠pre维护一个变量的状态。如果题目中的约束条件包含多个变量，要想办法组合成一个变量
不同点是，计数类的hash table记录pre中各状态已经出现的次数，最值类的hash table记录的是pre中各状态最早出现的下标

5.未完待续

更确切地说，上面提到的约束性，指的是计算型的约束，如求和为k的连续子串，需要计算前缀和。对于计算型的约束，我们应用pre保存计算得到的被约束的变量值，再用hash记录变量值在pre中已经出现的次数或者最早出现的位置，组合起来求解

实际上，还有【另外一类约束性连续子串问题】，也就是统计型的约束。这时，约束不是通过计算产生的，而是通过统计，即这个子串内是否包含了特定字符并且达到相应的个数。
其实，这就是【滑动窗口】问题，这个连续的子串就是一个滑动窗口