Leetcode-每日一题【剑指 Offer II 009. 乘积小于 K 的子数组】
题目
给定一个正整数数组 nums和整数 k ,请找出该数组内乘积小于 k 的连续的子数组的个数。
示例 1:
输入: nums = [10,5,2,6], k = 100
输出: 8
解释: 8 个乘积小于 100 的子数组分别为: [10], [5], [2], [6], [10,5], [5,2], [2,6], [5,2,6]。
需要注意的是 [10,5,2] 并不是乘积小于100的子数组。
示例 2:
输入: nums = [1,2,3], k = 0
输出: 0
提示:
- 1 <= nums.length <= 3 * 104
- 1 <= nums[i] <= 1000
- 0 <= k <= 106
解题思路
前置知识
滑动窗口
(1)滑动窗口可以用以解决数组/字符串的子元素相关问题,并且可以将嵌套的循环问题,转换为单循环问题,从而降低时间复杂度。故滑动窗口算法的复杂度一般为 O(n)。
(2)滑动窗口的基本思想如下:
首先使用双指针维护一个子数组,别称为 left 和 right。left 指向窗口的左端点,right 指向窗口的右端点。如下图所示:
窗口随着 right 指针向右滑动开始遍历整个数组区间(即增大窗口);
而在每次迭代内部(即针对每一次 right)要对子数组区间是否满足要求进行判断。如果子数组区间不能够满足条件则将 left 指针向右移动(即缩小窗口),这样窗口就实现了向右滑动。
知道了滑动窗口后,我们来看一下这道题
1.题目要求我们求出 数组内乘积小于 k 的连续的子数组的个数,一般求解子数组这类题我们都会用到滑动数组,这道题也不例外
2.首先我们设置好要用到的变量,curr 用来存放子数组的乘积,sum 用来统计符合条件的子数组的个数,i 作为滑动窗口中窗口的左边界。
3.我们for循环对数组进行遍历,每当 j 遍历一个元素后就把它乘进 curr 中,然后用while循环去判断这个滑动窗口内的乘积是否大于k,若大于k 我们就将滑动窗口最左边的一个元素从curr中除去,并将滑动窗口的左边界向右移动一个,直到滑动窗口内的乘积小于k,我们就把结果加到sum中,注意这里的 right - left + 1 就是以当前窗口右界为最后一个元素的连续子序列的个数。这么做的道理是这样的。如果一个长度为 n 的序列中的任意长度连续子序列都满足要求,那么这些子序列可以无重复无遗漏地划分为 n 组,组内子序列尾元素相同,组间尾元素互异。
举个例子:
思路: 设存在数组nums=[A, B, C, D], k为乘积, count为符合条件的数组个数, i,j为窗口左右边界;*(假设) A: A<k i=j=0 --> count = A (0-0+1)* B: AB<k j=1 --> count = AB, B(1-0+1)* C: ABC>=k j=2 --> BC<k i=1 --> count = BC, C (2-1+1)* D: BCD>k j=3 --> CD>K i=2 --> D < k i=3 --> count = D (3-3+1)* 当计算的数组乘积大于k时,将窗口左边界右移, 直到小于k, 计算count,窗口右边界右移;* 当计算的数组乘积小于k时,计算count,窗口右边界右移* 得出规律:每一次遍历count增加了j-i+14.最后返回sum即可。
代码实现
class Solution {public int numSubarrayProductLessThanK(int[] nums, int k) {int n = nums.length;int curr = 1, sum = 0, i = 0; for(int j = 0; j < n; j++){curr *= nums[j];while(i <= j && curr >= k ){curr /= nums[i];i++;}sum += j - i + 1;}return sum;}
}
测试结果

hh
相关文章:
Leetcode-每日一题【剑指 Offer II 009. 乘积小于 K 的子数组】
题目 给定一个正整数数组 nums和整数 k ,请找出该数组内乘积小于 k 的连续的子数组的个数。 示例 1: 输入: nums [10,5,2,6], k 100输出: 8解释: 8 个乘积小于 100 的子数组分别为: [10], [5], [2], [6], [10,5], [5,2], [2,6], [5,2,6]。 需要注意的是 [10,5,2]…...
html/javascript-表格的创建和使用
html中表格的创建和使用 一 摘要二 使用html table标签创建表格(在html文件中)三 使用javascript创建表格(在js文件中)四 表格属性的设置:4.1. 右边框的设置:4.2. 只给表格单元格加右边框4.3. 动态设置右边…...
[点微]同城原生微信小程序 小程序原生版 1.0.7(tom_xiaofenlei)
注意!!!这是点微后出的原生版小程序!!! 依赖点微同城分类主插件、点微同城小程序后端插件!!! 【以下为模块路径】 同城首页 pages/index/index 个人中心 pages/index/my 好店首页 pages/module/tcshop 商城首页 pages/module/tcmall 抢购首页 pages/module/tcqianggou…...
JDBC Some Templates
JDBCTemplate 是Spring对JDBC的封装,使用JDBCTemplate方便实现对数据的操作。 <!-- orm:Object relationship mapping m对象 关系 映射-->引入依赖 <!-- 基于Maven依赖的传递性,导入spring-content依赖即可导入当前所需的所有…...
dubbo启动指定ip不使用docker虚拟网络ip
java -D 配置系统属性 # 启动时加参数 -DDUBBO_IP_TO_REGISTRY 192.168.1.1 该ip为dubbo所在服务器的公网ip即可。 java -jar myDubboRpc-api.jar -DDUBBO_IP_TO_REGISTRY 192.168.1.1 # xjar启动 nohup ./xjar java -DDUBBO_IP_TO_REGISTRY11.22.33.44 -XX:UseG1GC -jar …...
Bobo String Construction
登录—专业IT笔试面试备考平台_牛客网 题目大意:给出一字符串t,求一个长为n的字符串,使tst中包含且仅包含两个t 1<n<1000;测试样例组数<1000 思路:一开始很容易想到如果t里有1,s就全0,否则s就全…...
基于java在线个人网站源码设计与实现
摘 要 随着社会及个人社交应用平台的飞速发展,人们的沟通成本逐渐降低,互联网信息的普及也进一步提升了人们对于信息的需求度,通过建立个人网站的方式来展示自己的生活信息同时利用平台结交新的朋友,借助个人网站平台的搭建不仅可…...
Ubuntu18.04下编译qgc源码
写在前面 在下载前必须说明,根据你的qgc源码版本进行下载,有的源码必须要求Qt是5.15版本以上。 个人所使用开发软件 版本QT5.12.9qgc源码V4.0Ubuntu18.04 QT下载 (1)我们可以去官网下载官网下载地址具体的下载方法这里不用多说&a…...
Ros2_windows_install的学习笔记
Ros2_windows_install安装 Iron安装 iex ((New-Object System.Net.WebClient).DownloadString(https://raw.githubusercontent.com/scottcandy34/ros2_windows_install/main/ros2_iron.ps1))启动Iron C:\dev\ros2_iron\local_setup.bat...
5、Kubernetes核心技术 - Controller控制器工作负载
目录 一、Deployments - 控制器应用 二、Deployment升级回滚和弹性收缩 2.1、创建一个 1.14 版本的 pod 2.2、应用升级 2.3、查看升级状态 2.4、查看历史版本 2.5、应用回滚 2.6、弹性伸缩 三、StatefulSet - 有状态应用 四、DaemonSet - 守护进程 五、Job - 单次任…...
【java设计模式】创建型模式介绍(工厂模式、抽象工厂模式、单例模式、建造者模式、原型模式)
文章目录 简介一、工厂模式介绍案例 二、抽象工厂模式介绍案例 三、单例模式介绍案例 四、建造者模式介绍案例 五、原型模式介绍案例 简介 本文介绍Java设计模式中创建型模式的五种 一、工厂模式 工厂模式(Factory Pattern)是 Java 中最常用的设计模式…...
Redis系列:Redis 的事务机制
1 复习下何为事务机制? Transaction(事务)是计算机的特有术语,它一般指单个逻辑工作单位,由一系列的操作组合而成,在这些操作执行的时候,要么都执行成功,要么都不执行,防…...
动静态网页、Django创建表关系、Django框架的请求生命周期流程图
一、request对象的几个方法 在视图函数中写方法的时候,都会有一个形参requestdef index(request):passrequest.method # GET POST request.GET.get() # 它获取最后一个元素值 request.GET.getlist() # 获取到所有的request.POST.get() # 它获取最后一个元素值 req…...
神经网络的初始化方法
文章目录 1、随机初始化2、Xavier初始化3、He初始化4、权重预训练初始化5、零初始化 对于神经网络的训练过程中,合适的参数初始化方法有助于更好的处理梯度消失和梯度爆炸问题。通常有以下几种初始化方法: 1、随机初始化 随机初始化(Random…...
【SQL Server】DBCC CHECKDB只是一个数据库维护命令吗?
日期:2023年7月27日 作者:Commas 签名:(ง •_•)ง 积跬步以致千里,积小流以成江海…… 注释:如果您觉得有所帮助,帮忙点个赞,也可以关注我,我们一起成长;如果有不对的地方…...
三、Web安全相关知识
请勿用于非法用途 文章目录 一、Web源码框架二、目录结构1、静态资源2、WEB-INF(1)classes(2)lib(3)web.xml 二、web脚本语言1、脚本种类(1)ASP(2)ASP.NET&am…...
Android系统服务之AMS
目录 概述 重点和难点问题 启动方式 main入口: run方法: BootstrapSevices 小结: 与其他线程的通信原理 参考文档: 概述 AMS是Android系统主要负责四大组件的启动,切换,调度以及应用程序进程管理和调度等工…...
Unity UGUI的EventTrigger (事件监听器)组件的介绍及使用
Unity UGUI的EventTrigger (事件监听器)组件的介绍及使用 1. 什么是EventTrigger组件? EventTrigger是Unity UGUI中的一个组件,用于监听和响应UI元素的各种事件,例如点击、拖拽、进入、离开等。通过EventTrigger组件,我们可以方…...
Matlab的SimuLink对FS32K144编程--内部数据存储Flash
前言 Flah擦写是由寿命的,应当减免无效的擦写,如数据值不变不进行擦写 1、新建工程完成后,拖出Flash的存储控制初始化…...
【MySQL】centos 7下MySQL的环境搭建
从本期博客开始我们正式进入到数据库的学习,在学习数据库时所用到的工具是Linux环境下的MySQL 目录 一、检查环境中是否装有MySQL 二、获取MySQL官方yum源 三、配置MySQL官方yum源 四、一键安装MySQL 五、启动mysql服务 六、登录MySQL 七、修改mysql配置文件…...
idea大量爆红问题解决
问题描述 在学习和工作中,idea是程序员不可缺少的一个工具,但是突然在有些时候就会出现大量爆红的问题,发现无法跳转,无论是关机重启或者是替换root都无法解决 就是如上所展示的问题,但是程序依然可以启动。 问题解决…...
【Python】 -- 趣味代码 - 小恐龙游戏
文章目录 文章目录 00 小恐龙游戏程序设计框架代码结构和功能游戏流程总结01 小恐龙游戏程序设计02 百度网盘地址00 小恐龙游戏程序设计框架 这段代码是一个基于 Pygame 的简易跑酷游戏的完整实现,玩家控制一个角色(龙)躲避障碍物(仙人掌和乌鸦)。以下是代码的详细介绍:…...
label-studio的使用教程(导入本地路径)
文章目录 1. 准备环境2. 脚本启动2.1 Windows2.2 Linux 3. 安装label-studio机器学习后端3.1 pip安装(推荐)3.2 GitHub仓库安装 4. 后端配置4.1 yolo环境4.2 引入后端模型4.3 修改脚本4.4 启动后端 5. 标注工程5.1 创建工程5.2 配置图片路径5.3 配置工程类型标签5.4 配置模型5.…...
R语言AI模型部署方案:精准离线运行详解
R语言AI模型部署方案:精准离线运行详解 一、项目概述 本文将构建一个完整的R语言AI部署解决方案,实现鸢尾花分类模型的训练、保存、离线部署和预测功能。核心特点: 100%离线运行能力自包含环境依赖生产级错误处理跨平台兼容性模型版本管理# 文件结构说明 Iris_AI_Deployme…...
对WWDC 2025 Keynote 内容的预测
借助我们以往对苹果公司发展路径的深入研究经验,以及大语言模型的分析能力,我们系统梳理了多年来苹果 WWDC 主题演讲的规律。在 WWDC 2025 即将揭幕之际,我们让 ChatGPT 对今年的 Keynote 内容进行了一个初步预测,聊作存档。等到明…...
Spring Cloud Gateway 中自定义验证码接口返回 404 的排查与解决
Spring Cloud Gateway 中自定义验证码接口返回 404 的排查与解决 问题背景 在一个基于 Spring Cloud Gateway WebFlux 构建的微服务项目中,新增了一个本地验证码接口 /code,使用函数式路由(RouterFunction)和 Hutool 的 Circle…...
管理学院权限管理系统开发总结
文章目录 🎓 管理学院权限管理系统开发总结 - 现代化Web应用实践之路📝 项目概述🏗️ 技术架构设计后端技术栈前端技术栈 💡 核心功能特性1. 用户管理模块2. 权限管理系统3. 统计报表功能4. 用户体验优化 🗄️ 数据库设…...
Go 并发编程基础:通道(Channel)的使用
在 Go 中,Channel 是 Goroutine 之间通信的核心机制。它提供了一个线程安全的通信方式,用于在多个 Goroutine 之间传递数据,从而实现高效的并发编程。 本章将介绍 Channel 的基本概念、用法、缓冲、关闭机制以及 select 的使用。 一、Channel…...
LLaMA-Factory 微调 Qwen2-VL 进行人脸情感识别(二)
在上一篇文章中,我们详细介绍了如何使用LLaMA-Factory框架对Qwen2-VL大模型进行微调,以实现人脸情感识别的功能。本篇文章将聚焦于微调完成后,如何调用这个模型进行人脸情感识别的具体代码实现,包括详细的步骤和注释。 模型调用步骤 环境准备:确保安装了必要的Python库。…...
热门Chrome扩展程序存在明文传输风险,用户隐私安全受威胁
赛门铁克威胁猎手团队最新报告披露,数款拥有数百万活跃用户的Chrome扩展程序正在通过未加密的HTTP连接静默泄露用户敏感数据,严重威胁用户隐私安全。 知名扩展程序存在明文传输风险 尽管宣称提供安全浏览、数据分析或便捷界面等功能,但SEMR…...



