Leetcode--713. 乘积小于k的子数组
初始化指针:使用两个指针left和right,分别从数组的左端和右端开始移动。 遍历数组:从右指针开始遍历数组,逐步扩大当前窗口的大小。 计算乘积:每次将当前元素乘到乘积变量t中。 调整左指针:当乘积t大于等于k时,将左指针向右移动,并将乘积变量t除以 nums[left],同时记录left的位置。 统计子数组数量:在满足条件的情况下,记录当前窗口中满足条件的子数组数量。 初始条件检查:首先检查k是否小于等于1,直接返回0,因为没有任何子数组的乘积小于k。 乘积变量t:初始化为1,用于记录当前窗口内所有元素的乘积。 遍历数组:从数组的左端开始,逐步扩大右指针的范围。 乘积计算与调整:每次将当前元素乘到t中,然后检查t是否大于等于k,如果大于等于,调整左指针,同时将t除以当前移动的元素,确保乘积小于k。 统计结果:每次调整完左指针后,计算当前窗口中满足条件的子数组数量,并累加到结果中。 返回结果:遍历结束后,返回满足条件的子数组总数。
发布日期:2021-04-30 21:01:28
浏览次数:120
分类:精选文章
本文共 1218 字,大约阅读时间需要 4 分钟。
代码解释与优化思路
以下是基于双指针法解决的问题的详细解释和代码实现。这种方法能够高效地解决问题,时间复杂度为O(n),适用于处理大规模数据。
方法思路
我们使用双指针法来解决这个问题,具体步骤如下:
这种方法利用了双指针技术,能够在O(n)的时间复杂度内完成任务,非常适合处理大规模数据。
代码解释
public class Solution713 { public static int numSubarrayProductLessThanK(int[] nums, int k) { if (k <= 1) return 0; int t = 1; int ans = 0; int left = 0; for (int right = 0; right < nums.length; right++) { t *= nums[right]; while (t >= k) { t /= nums[left++]; } ans += right - left + 1; } return ans; } public static void main(String[] args) { int[] nums = {10,5,2,6}; int k = 100; System.out.println(numSubarrayProductLessThanK(nums, k)); }} 代码优化思路
这种方法通过双指针技术,确保了在遍历数组时,每次只需要进行常数时间的操作,从而保证了算法的高效性。
发表评论
最新留言
路过,博主的博客真漂亮。。
[***.116.15.85]2026年06月01日 10时28分01秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
rabbitmq重启
2023-03-01
php实现上传(多个)文件函数封装
2023-03-01
php实现下载文件方法
2023-03-01
php实现单链表
2023-03-01
php实现图片背景换色功能
2023-03-01
php实现多个一维数组对应合并成二维数组
2023-03-01
php实现多关键字查找方法
2023-03-01
PHP实现微信公众号H5支付
2023-03-01
PHP实现微信公众号网页授权
2023-03-01
PHP实现微信小程序推送消息至公众号
2023-03-01
rabbitmq逻辑与开发
2023-03-01
php实现根据身份证获取年龄
2023-03-01
PHP实现的MongoDB数据增删改查
2023-03-01
PHP实现的SSO单点登录系统,拿走就用吧
2023-03-01
php实现短信验证功能
2023-03-01
php实现逆转数组
2023-03-01
PHP实现通过geoip获取IP地理信息
2023-03-01
PHP实现页面静态化、纯静态化及伪静态化
2023-03-01
php容许ajax跨域,PHP设置允许ajax跨域请求的两种常见方法
2023-03-01