LWC 55:713. Subarray Product Less Than K

LWC 55:713. Subarray Product Less Than K

传送门:713. Subarray Product Less Than K

Problem:

Your are given an array of positive integers nums. Count and print the number of (contiguous) subarrays where the product of all the elements in the subarray is less than k.

Example 1:

Input: nums = [10, 5, 2, 6], k = 100 Output: 8 Explanation: The 8 subarrays that have product less than 100 are: [10], [5], [2], [6], [10, 5], [5, 2], [2, 6], [5, 2, 6]. Note that [10, 5, 2] is not included as the product of 100 is not strictly less than k.

Note:

0 < nums.length <= 50000.

0 < nums[i] < 1000.

0 <= k < 10^6.

思路: 尺取法的思想,连续的子数组,且在指定范围k内,所以不可能无限乘下去,采用双指针{lf, rt},一旦乘积大于等于k,则可以停止后续的搜索,同理一旦超过k,那么lf也需要更新。

更新规则: 比如[10,5],当rt 搜索到5时,lf 搜索到10时,从5出发的子数组有[10, 5] 和[5],所以cnt += rt - lf + 1即可。

代码如下:

    public int numSubarrayProductLessThanK(int[] nums, int k) {
        int cnt = 0;
        int n = nums.length;

        int p = 1;
        int j = 0;
        for (int i = 0; i < n; ++i) {
            p *= nums[i];
            if (p < k) {
                cnt += i - j + 1;            
            }
            else { // p >= k
                for (; j < n; ){
                    p /= nums[j++];
                    if (p < k) break;
                }
                if (p < k) cnt += i - j + 1;
            }
        }
        return cnt;
    }     

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏MasiMaro 的技术博文

windows错误处理

在调用windows API时函数会首先对我们传入的参数进行校验,然后执行,如果出现什么情况导致函数执行出错,有的函数可以通过返回值来判断函数是否出错,比如对于...

892
来自专栏玩转JavaEE

MongoDB文档查询操作(二)

上篇文章我们对MongoDB中的查询操作做了简单介绍,本文我们继续来看更丰富的查询操作。 本文是MongoDB系列的第六篇文章,了解前面的文章有助于更好的理解本...

3173
来自专栏spring源码深度学习

java基础io流——File的告白(重温经典)

创建成功返回true,如果存在就不创建返回false,创建一个文件时需要确保当前文件夹存在,所有要异常处理。

1233
来自专栏Fish

android文件存储

为了输出数据,要把list中存储的写到一个txt文件里,就顺手学了一下 文件存储的方法,说是学,其实又是百度之后复制粘贴。不过学到了一个关于java中的一个知识...

2119
来自专栏Web项目聚集地

手写一个Mybatis框架

在手写自己的Mybatis框架之前,我们先来了解一下Mybatis,它的源码中使用了大量的设计模式,阅读源码并观察设计模式在其中的应用,才能够更深入的理解源...

892
来自专栏流媒体

resources.arsc解析

示例apk 示例代码 binary view二进制文件查看工具: android 6.0系统源码(网上搜索下载,这里暂不提供资源)

1252
来自专栏chenssy

【死磕Sharding-jdbc】---group by结果合并(2)

在sharding-jdbc源码之group by结果合并(1)中主要分析了sharding-jdbc如何在GroupByStreamResultSetMerg...

892
来自专栏风口上的猪的文章

.NET面试题系列[13] - LINQ to Object

"C# 3.0所有特性的提出都是更好地为LINQ服务的" - Learning Hard

912
来自专栏IMWeb前端团队

Redux源码解析系列(四)-- combineReducers

本文作者:IMWeb 黄qiong 原文出处:IMWeb社区 未经同意,禁止转载 combindeReducer 字面意思就是用来合并reducer的...

1887
来自专栏玩转JavaEE

MongoDB文档查询操作(一)

上篇文章我们主要介绍了MongoDB的修改操作,本文我们来看看查询操作。 本文是MongoDB系列的第五篇文章,了解前面的文章有助于更好的理解本文: ---- ...

3456

扫码关注云+社区