Leetcode--713. 乘积小于k的子数组
发布日期:2021-04-30 21:01:28 浏览次数:120 分类:精选文章

本文共 1218 字,大约阅读时间需要 4 分钟。

代码解释与优化思路

以下是基于双指针法解决的问题的详细解释和代码实现。这种方法能够高效地解决问题,时间复杂度为O(n),适用于处理大规模数据。

方法思路

我们使用双指针法来解决这个问题,具体步骤如下:

  • 初始化指针:使用两个指针left和right,分别从数组的左端和右端开始移动。
  • 遍历数组:从右指针开始遍历数组,逐步扩大当前窗口的大小。
  • 计算乘积:每次将当前元素乘到乘积变量t中。
  • 调整左指针:当乘积t大于等于k时,将左指针向右移动,并将乘积变量t除以 nums[left],同时记录left的位置。
  • 统计子数组数量:在满足条件的情况下,记录当前窗口中满足条件的子数组数量。
  • 这种方法利用了双指针技术,能够在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));    }}

    代码优化思路

  • 初始条件检查:首先检查k是否小于等于1,直接返回0,因为没有任何子数组的乘积小于k。
  • 乘积变量t:初始化为1,用于记录当前窗口内所有元素的乘积。
  • 遍历数组:从数组的左端开始,逐步扩大右指针的范围。
  • 乘积计算与调整:每次将当前元素乘到t中,然后检查t是否大于等于k,如果大于等于,调整左指针,同时将t除以当前移动的元素,确保乘积小于k。
  • 统计结果:每次调整完左指针后,计算当前窗口中满足条件的子数组数量,并累加到结果中。
  • 返回结果:遍历结束后,返回满足条件的子数组总数。
  • 这种方法通过双指针技术,确保了在遍历数组时,每次只需要进行常数时间的操作,从而保证了算法的高效性。

    上一篇:Java语言的特性
    下一篇:SSM学习笔记(8)_MyBatis_Day02_CRUD/配置文件

    发表评论

    最新留言

    路过,博主的博客真漂亮。。
    [***.116.15.85]2026年06月01日 10时28分01秒