题解 | #能被多个质数整除的第K长子段#

注意到，如果对于给定的区间左边界l，若满足题目条件的区间右边界最大为r，那么显然(l,r)的任意子区间也是满足条件的，也即固定区间左边界为(l,r)中任取的i，区间右边界至少为r。因此不需要记录每一个满足条件的区间对(i,j)再进行排序，而只需要对于左边界l从0到n-1遍历，查找并记录满足条件的最大区间长度，最后对这n个数做逆序排序输出第K个大长度即可。

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 求满足条件的第K大长度
# @param A int整型一维数组 牛牛的数组A
# @param X int整型 至少要存在X个不同的质数
# @param K int整型 牛牛希望找到第K大的长度
# @return int整型
#
primes=[]
factors=[]

class Solution:
    def getprimes(self,n):
        if n<2:
            return
        primes.append(2)
        i=3
        while i<=n:
            flag=True
            for p in primes:
                if i%p==0:
                    flag=False
                    break
            if flag:
                primes.append(i)
            i+=2
        return

    def getfactors(self,a):
        fac=[]
        for p in primes:
            if p>a:
                break
            if a%p==0:
                fac.append(p)
        return fac

    def GetKthLength(self , A , X , K ):
        # write code here
        n=max(A)
        self.getprimes(n)
        A_facs=[]
        for a in A:
            A_facs.append(self.getfactors(a))
        l=len(A)
        ints=[]
        for i in range(l):
            if len(A_facs[i])<X:
                ints.append(0)
                continue
            commonfac=A_facs[i]
            j=i+1
            while j<l:
                cnt=0
                for p in commonfac:
                    if p in A_facs[j]:
                        cnt+=1
                if cnt<X:
                    break
                j+=1
            ints.append(j-i)
        if len(ints)<K:
            return -1
        else:
            ints.sort(reverse=True)
            return ints[K-1]