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 条评论
登录 后参与评论

相关文章

来自专栏静晴轩

lua Standard Libraries

The standard Lua libraries provide useful functions that are implemented directl...

2689
来自专栏吾真本

CYBER-DOJO.ORG上的编程操练题目100 doorsAnagramsBalanced ParenthesesBowling GameCalc StatsCombined NumberCoun

Cyber-dojo.org是编程操练者的乐园。下面是这个网站上的43个编程操练题目,供编程操练爱好者参考。

802
来自专栏康怀帅的专栏

CoreOS 配置工具 Ignition v2.2

This pre-release version of the specification is experimental and is subject to ...

3416
来自专栏开源优测

屌爆了,一句话描述各种编程语言

Python: What if everything was a dict? Java: What if everything was an object? J...

34810
来自专栏小樱的经验随笔

HDU 4256 The Famous Clock

The Famous Clock Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/3...

2656
来自专栏算法修养

CodeForces 665A Buses Between Cities

A. Buses Between Cities time limit per test 1 second memory limit per test ...

2774
来自专栏ml

HDUOJ-------The Hardest Problem Ever

The Hardest Problem Ever Time Limit: 2000/1000 MS (Java/Others)    Memory Limit:...

34810
来自专栏算法修养

Code Forces 645A Amity Assessment

A. Amity Assessment time limit per test2 seconds memory limit per test256 me...

1804
来自专栏小樱的经验随笔

UVA 11292 Dragon of Loowater(简单贪心)

Problem C: The Dragon of Loowater Once upon a time, in the Kingdom of Loowater, ...

2657
来自专栏数据结构与算法

POJ 1985 Cow Marathon(树的直径)

Description After hearing about the epidemic of obesity in the USA, Farmer John...

3256

扫码关注云+社区