今天这道题目适合用双指针来解决

题目描述

  题目链接,713. 乘积小于 K 的子数组。题目截图如下:

image-20220505134830466

题目分析

  首先说一下题目意思,其实就是满足如下要求:

  • 找子数组,并且子数组数连续的,就是下标元素是连续的
  • 子数组里的所有元素乘积小于给定的k

  这道题一般人的思路就是两个循环,一个枚举起点,一个枚举终点,保证起点小于等于终点,然后计算之间的乘积,然后判断与k的大小,小于k就计数加一。但是这个思路会超时,本人尝试过。

  所以我们可以尝试使用双指针的思路,首先,两个指针都指向下标0,然后我们固定左指针,移动右指针。每次移动的时候计算目前左指针到右指针之间所有元素的乘积,只要乘积小于k,我们就计算两个指针之间的元素长度(right-left+1),然后将这个值加到我们的res中。一旦目前的值大于等于k,我们就移动左指针的下标,每移动一次就将乘积除以一个nums[left],直到值小于k,就停止,因为我们最开始是找[left,right]之间所有连续子数组乘积小于k的个数,既然目前乘积大于等于k了,我们就移动左指针(因为要求是连续子数组),来保证乘积小于k。我们以实例1为例子,画出下图做解释。

image-20220505142928414

  最后,通俗一点做个总结。也就是首先通过固定左端点,找到最大的右端点部分,并且将这期间的满足条件的子数组数目累加起来。之后固定右端点来找满足条件的左端点,然后将满足条件的子数组数目加起来。

代码实现

  c++代码实现如下:

class Solution {
public:
    int numSubarrayProductLessThanK(vector<int>& nums, int k) {
        int n = nums.size(),res = 0;
        int value = 1,i = 0;
        for(int j = 0;j<n;j++){
            // 枚举终点
            value*=nums[j];
            while(i<=j && value>=k){
                // 一旦发现大于等于k 将左边的除掉直到乘积小于k
                value/=nums[i];
                i++;
            }
            res += j-i+1;
        }
        return res;
    }
};

结语

 手握长剑,莫负良人!

Q.E.D.


  Java后端开发工程师一名,北漂一族,欢迎大家前来交流