【leetcode算法】——713. 乘积小于k的子数组

滑动窗口

713. 乘积小于k的子数组

滑动窗口：
关键点：
1、不定长滑动窗口
2、cnt += r - l + 1；

解题思路：
nums = [10,5,2,6], k = 100

1. r = 0， prot = 10， 小于k， cnt = 1 [10]
2. r = 1， prot = 10 * 5，小于k，cnt = r - l +1 = 2 [10,5] [5]
3. r = 2， prot = 10 * 5 *2，大于k， l++，cnt = r - l + 1 = 2；[5,2] [2]
4. r = 3, prot = 5 * 2 * 6， 小于k， cnt = r - l + 1 = 3 ;[5,2,6] [2,6] [6]
5. cnt = 8;

class Solution {
public:
    int numSubarrayProductLessThanK(vector<int>& nums, int k) {
        // 初始化数目为0
        int cnt = 0;
        // 乘积为1
        int prot = 1;
        // 左端点
        int l = 0;

        if(k <= 1)
        {
            return 0;
        }  

        for(int r = 0; r<nums.size();++r)
        {
            prot *=nums[r];
            // 当乘积的值大于k，缩小左端点
            while(prot >= k)
            {
                prot /=nums[l++];
            }
            // 求和
            cnt += r - l +1;
        }
        return cnt;
    }
};

原文地址：https://blog.csdn.net/weixin_45035977/article/details/142855493

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！