[数据结构与算法] 双指针乘积小于 K 的子数组

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> 双指针乘积小于 K 的子数组 -> 正文阅读

[数据结构与算法]双指针乘积小于 K 的子数组

双指针从广义上来说，是指用两个变量在线性结构上遍历而解决的问题。狭义上说，

对于数组，指两个变量在数组上相向移动解决的问题；
对于链表，指两个变量在链表上同向移动解决的问题，也称为「快慢指针」问题。
双指针算法通常不难，双指针算法是基于暴力解法的优化，它们是很好的学习算法的入门问题。

713. 乘积小于 K 的子数组
在这里插入图片描述

class Solution {
public:
    int numSubarrayProductLessThanK(vector<int>& nums, int k) {
        if(k<=1)                   // 处理特殊情况
            return 0;
        int res = 0;        
        int left=0,right=0;          // 左右指针
        int sum=1;                   // 乘积
        while(right<nums.size()){
            sum*=nums[right];
            while(sum>=k){
                sum/=nums[left];
                //res+=right-left;       错误！
                left++;
            }
            res+=right-left+1;           // 这里比较难以理解 ！
            right++;
        }
        return res;
    }
};

这里是每次右指针移动时，更新结果。
这里每次更新结果的统计是这样的，以[10,5,2,6]为例，
L=0,R=0; [10]
L=0,R=1; [5],[10,5]
L=1,R=2;[2],[2,5]
L=1,R=3;[6],[2,6],[5,2,6]
可以看出每次是以右指针为基准向左移动的；
如果按照我开始的理解，在左指针移动时更新结果，这是错误的！
L=0,R=2;[10],[10,5]
L=1,R=3;[5],[5,2],[5,2,6]
这样后面比k小的乘积便不会被统计，所以是错误的。