灵神基础算法精讲-03-学习笔记

209. 长度最小的子数组

给定一个含有 n 个正整数的数组和一个正整数 target 。

找出该数组中满足其总和大于等于 target 的长度最小的子数组 [numsl, numsl+1, …, numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。

暴力做法

枚举子数组的左端点，不断向右扩展，直到达到target为止；也可以枚举子数组的右端点，不断向左扩展，直到达到target为止。

思路

利用正整数这个性质，枚举左端点时，如果已经找到几个数的和大于等于target了，可以向右扩展左端点，直到和小于target。

做法

初始化ans为n+1或inf(答案至多为n)，子数组左端点left为0，子数组的和sum为0，枚举子数组右端点，for right, x in enumerate(nums)，累加子数组右端点的值，当sum >= target时，记录当前ans = min(ans, right - left + 1)，将子数组左端点向右扩展，即sum -= nums[left]，left += 1。最后return ans if ans <= n else 0。

class Solution:
    def minSubArrayLen(self, target, nums):
        
        n = len(nums)
        ans = n + 1
        left = 0
        sum = 0
        for right, x in enumerate(nums):
            sum += x
            while sum >= target:
                ans = min(ans, right - left + 1)
                sum -= nums[left]
                left += 1
        return ans if ans <= n else 0
    
if __name__ == '__main__':
    solution = Solution()
    target = 7
    nums = [2,3,1,2,4,3]
    print(solution.minSubArrayLen(target, nums))

713. 乘积小于K的子数组

给你一个整数数组 nums 和一个整数 k ，请你返回子数组内所有元素的乘积严格小于 k 的连续子数组的数目。

思路

枚举子数组右端点，向右扩展右端点，如果子数组乘积大于等于K时，就把左端点向右移动，缩小子数组的长度，直到乘积小于k为止。假设目前子数组为[l,r]，计算以r为右端点的子数组的个数，注意右端点是固定的，如果从l到r的这一段的乘积是小于K的，那么从l+1到r这一段乘积也是小于K的，一直到[r,r]这些子数组都是满足要求的，那么子数组的个数其实就是从l到r的元素个数，即 r-l+1。

做法

首先判断极端条件，当k <= 1时，题目要求乘积严格小于k，而nums为整数数组，因此返回0。初始化left = 0，prod = 1，枚举右端点for right, x in enumerate(nums)，不断累乘x，当prod >= k时，向右扩展左端点，prod /= nums[left]， left += 1，跳出循环，计算ans += right - left + 1，最后return ans。

class Solution:
    def numSubarrayProductLessThanK(self, k, nums):
        if k <= 1:
            return 0
        left = 0
        prod = 1
        ans = 0
        for right, x in enumerate(nums):
            prod *= x
            while prod >= k:
                prod /= nums[left]
                left += 1
            ans += right - left + 1
        return ans
    
if __name__ == '__main__':
    solution = Solution()
    k = 100
    nums = [10,5,2,6]
    print(solution.numSubarrayProductLessThanK(k, nums))

3. 无重复字符的最长子串

给定一个字符串 s ，请你找出其中不含有重复字符的最长子串的长度。

做法

初始化ans = 0，cnt = Counter()，cnt是一个哈希map，它的key是char，value是int。枚举子数组右端点，每次将这个字符出现的次数加一，即cnt[c] += 1，当发现有重复字符时，右移左端点，直到没有重复字符为止，由于每次都是接到一个没有重复字符的子串后面，所以这个重复的字符一定来自于接入的字符。用一个哈希表来记录字符的出现次数。即while cnt[c] > 1，

from collections import Counter

class Solution:
    def lengthOfLongestSubstring(self, s):
        left = ans = 0
        cnt = Counter()
        for right, x in enumerate(s):
            cnt[x] += 1
            while cnt[x] > 1:
                cnt[s[left]] -= 1
                left += 1
            ans = max(ans, right - left + 1)
        return ans
    
if __name__ =='__main__':
    solution = Solution()
    s = "abcabcbb"
    print(solution.lengthOfLongestSubstring(s))