438.找到字符串中所有字母异位词

给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。异位词 指字母相同，但排列不同的字符串。

示例 1:
输入: s = "cbaebabacd", p = "abc"
输出: [0,6]
解释:
起始索引等于 0 的子串是 "cba", 它是 "abc" 的异位词。
起始索引等于 6 的子串是 "bac", 它是 "abc" 的异位词。

示例 2:
输入: s = "abab", p = "ab"
输出: [0,1,2]
解释:
起始索引等于 0 的子串是 "ab", 它是 "ab" 的异位词。
起始索引等于 1 的子串是 "ba", 它是 "ab" 的异位词。
起始索引等于 2 的子串是 "ab", 它是 "ab" 的异位词。

具体题目链接

Python

class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        left,s_p,len_p=0,len(s)-len(p),len(p)
        ls=[]
        s_list=[0]*26
        p_list=[0]*26
        if s_p<0:
            return ls
        for i in range(len_p):
            s_list[ord(s[i])-97]+=1
            p_list[ord(p[i])-97]+=1
        for i in range(left,s_p):
            if s_list==p_list:
                ls.append(i)
            s_list[ord(s[i])-97]-=1
            s_list[ord(s[i+len_p])-97]+=1
        if s_list==p_list:
            ls.append(s_p) 
        return ls

思路：首先先建立两个列表，p_list储存所有p中字符的个数，s_list储存当前滑动窗口的各字符个数，如果相同，则证明是异位词。

GO

func findAnagrams(s string, p string) []int {
    left,s_p,len_p:=0,len(s)-len(p),len(p)
    ls:=[]int{}
    if s_p<0{
        return ls
    }
    s_list:=[26]int{}
    p_list:=[26]int{}
    for i:=0;i<len(p);i++{
            s_list[s[i]-97]+=1
            p_list[p[i]-97]+=1
    }
    for i:=left;i<s_p;i++{
        if (s_list==p_list){
            ls=append(ls,i)
        }  
        s_list[s[i]-97]-=1
        s_list[s[i+len_p]-97]+=1
    }
    if (s_list==p_list){
        ls=append(ls,s_p)
        }  
    return ls
}

思路：同Python

713. 乘积小于K的子数组

给定一个正整数数组 nums和整数 k 。请找出该数组内乘积小于 k 的连续的子数组的个数。

示例 1:
输入: nums = [10,5,2,6], k = 100
输出: 8
解释: 8个乘积小于100的子数组分别为: [10], [5], [2], [6], [10,5], [5,2], [2,6], [5,2,6]。
需要注意的是 [10,5,2] 并不是乘积小于100的子数组。
示例 2:
输入: nums = [1,2,3], k = 0
输出: 0

具体题目链接

Python

class Solution:
    def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int:
        if k == 0 or k == 1: return 0
        lenght=len(nums)#总长度
        temp=1#保存当前计算的积
        left=0#左指针，区间最左侧
        right=0#右指针，区间最右侧
        sums=0#统计个数
        while right<lenght:
            temp*=nums[right]#每次要乘以当前右侧值
            while temp>=k:#判断是否大于等于k，若是则缩短左边界
                temp/=nums[left]
                left+=1
            sums+=right-left+1#原因如思路中所示
            right+=1
        return sums

思路：具体思路注释已解释，sums+=right-left+1的意思 我复制一位大佬的解释：[10, 5, 2, 6]，第一个满足条件的子串是[10]，第二个满足的是[10, 5]，但是第二个数组的子集[10]和前面的已经重复了，因此我们只需要计算包含最右边的数字的子串数量，就不会重复了，也就是在计算[10, 5]这个数组的子串是，只加入[5]和[10, 5]，而不加入[10]，这部分的子串数量刚好是right-left+1。

GO

func numSubarrayProductLessThanK(nums []int, k int) int {
    if k == 0 || k == 1{
        return 0
    }
    lenght,temp,left,right,sums:=len(nums),1,0,0,0
    for ;right<lenght;right++{
        temp*=nums[right]
        for ;temp>=k;left++{
             temp/=nums[left]
        }
        sums+=right-left+1
    }
    return sums
}

思路：同python

209. 长度最小的子数组

给定一个含有 n 个正整数的数组和一个正整数 target 。
找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。

示例 1：
输入：target = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组。
示例 2：
输入：target = 4, nums = [1,4,4]
输出：1
示例 3：
输入：target = 11, nums = [1,1,1,1,1,1,1,1]
输出：0

具体题目链接

Python

class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        length=len(nums)
        left=0
        right=0
        temp=0
        minLength=length+1
        while right<length:
            temp+=nums[right]
            while temp>=target:
                minLength=min(minLength,right-left+1)
                temp-=nums[left]
                left+=1
            right+=1
        return minLength if minLength!=length+1 else 0

思路：minLength是最短的数组长，初始情况下比全数组大1，原因是排除无解情况。其余是标准的滑动窗口和双指针。

GO

func minSubArrayLen(target int, nums []int) int {
    lenght,temp,left:=len(nums),0,0
    minLength:=lenght+1
    for right:=0;right<lenght;right++{
        temp+=nums[right]
        for ;temp>=target;left++{
            minLength=min(minLength,right-left+1)
            temp-=nums[left]
        }
    }
    if  minLength!=lenght+1{
        return minLength
    }
    return 0
}
func min(x,y int) int{
    if x<y{
        return x
    }
    return y
}

思路：同python