【Leetcode方法比较】DP/滑窗/前缀和

一、解决问题：连续子数组问题

二、适用原则：

　　1.滑窗：适合连续和/积问题，不适合有负值的问题，因为不知窗口往哪滑

　　2.前缀和/积：不适合数值过大的问题，因为前缀和/积数字可能超出数字表示范围

　　3.DP：适合子数组最大/最小问题，不适合和为k问题，因为要记录上一步的和/积，来更新当前步的和/积，但当前和/积难以确定来自前一步还是自身

三、实例：

　　1.【Leetcode-152】乘积最大子数组-适合DP，因为有负数且乘积可能超出范围

　　给你一个包含负数的整数数组 nums ，请你找出数组中乘积最大的连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。

def maxProduct(self, nums: List[int]) -> int:
        min_val = max_val = res = nums[0]
        for item in nums[1:]:
            min1, max1 = min_val, max_val
            max_val = max(min1*item, item, max1*item)
            min_val = min(min1*item, item, max1*item)
            res = max(res, max_val)
        return res

　　2.【Leetcode-560】和为K的子数组-适合前缀和，因为有负数且要求和为k

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

　　数组的长度为 [1, 20,000]。

　　数组中元素的范围是 [-1000, 1000] ，且整数 k 的范围是 [-1e7, 1e7]。

def subarraySum(self, nums: List[int], k: int) -> int:
        """
        前缀和
        [0,i]的和为total,以i为结尾的和为k的子数组个数为this_num,前缀和次数为pre_cnt,则this_num = pre_cnt[total - k]
        """
        from collections import defaultdict
        pre_cnt = defaultdict(int)  # 前缀和出现的次数
        pre_cnt[0] = 1  # 前缀和为0的有1种
        total = 0
        res = 0
        for item in nums:
            total += item  # 现在的前缀和
            this_num = pre_cnt[total - k]  # 满足差值为k的前缀和
            res += this_num
            pre_cnt[total] += 1
        return res

　　3.【Leetcode-713】乘积小于K的子数组-适合滑窗,因为乘积可能超出范围且要求和为k

　　给定一个正整数数组 nums。

　　找出该数组内乘积小于 k 的连续的子数组的个数。

　　0 < nums.length <= 50000，0 < nums[i] < 1000，0 <= k < 10^6

def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int:
        """
        前缀积，0~i的乘积为si,前缀积记录在look,则截止到i(包括i),<k的连续子数组数为look中key>si/k的数量之和+自身是否>k
        ！当数值可能较大时，前缀积也较大，可能无法计算，因此该方法只能数值小时使用！
        if k == 0:
            return 0
        look = {1: 1}
        pre_multi = 1
        res = 0
        for item in nums:
            pre_multi *= item
            # 前面提供的
            for pre, ct in look.items():
                if pre > pre_multi/k:
                    res += ct 
            # 更新
            cnt = look.get(pre_multi, 0)
            look[pre_multi] = cnt + 1
        return res
        """
        """
        滑窗
        """
        if k <= 1:
            return 0
        accumulate = 1  # 窗口内的积
        n = len(nums)
        res = 0
        start, end = 0, 0  # 窗口两端，结果需要包含end
        while end < n:
            accumulate *= nums[end]
            end += 1
            while accumulate >= k:
                accumulate /= nums[start]
                start += 1
            # 此刻满足条件，记录个数
            res += (end - start)  # start~end-1间，包含end的子数组个数
        return res