A
A
Algorithm Practice
Search…
A
A
Algorithm Practice
Introduction
Lintcode
Leetcode
Math
Tree
Graph
Two Pointers
3 Longest Substring Without Repeating Characters
11 Container With Most Water
15 3Sum
16 3Sum Closest
18 4Sum
26 Remove Duplicates from Sorted Array
27 Remove Element
30 Substring with Concatenation of All Words
42 Trapping Rain Water
76 Minimum Window Substring
80 Remove Duplicates from Sorted Array II
88 Merge Sorted Array
125 Valid Palindrome
159 Longest Substring with At Most Two Distinct Characters
167 Two Sum II - Input array is sorted
202 Happy Number
209 Minimum Size Subarray Sum
259 3Sum Smaller
283 Move Zeroes
340 Longest Substring with At Most K Distinct Characters
344 Reverse String
345 Reverse Vowels of a String
349 Intersection of Two Arrays
350 Intersection of Two Arrays II
360 Sort Transformed Array
395 Longest Substring with At Least K Repeating Characters
424 Longest Repeating Character Replacement
438 Find All Anagrams in a String
487 Max Consecutive Ones II
524 Longest Word in Dictionary through Deleting
532 K-diff Pairs in an Array
567 Permutation in String
611 Valid Triangle Number
632 Smallest Range
713 Subarray Product Less Than K
723 Candy Crush
763 Partition Labels
Linked List
Topological Sort
Hash Table
Trie
Sort
Binary Search
Heap
Breadth First Search
Stack
Backtracking
Dynamic Programming
Union Find
Scan Line
String
Reservoir Sampling
Recursion
Google
Powered By
GitBook
713 Subarray Product Less Than K
713.
Subarray Product Less Than K
1. Question
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:
1
Input: nums = [10, 5, 2, 6], k = 100
2
3
Output: 8
4
5
Explanation:
6
The 8 subarrays that have product less than 100 are: [10], [5], [2], [6], [10, 5], [5, 2], [2, 6], [5, 2, 6].
7
Note that [10, 5, 2] is not included as the product of 100 is not strictly less than k.
Copied!
Note:
0 < nums.length <= 50000
.
0 < nums[i] < 1000
.
0 <= k < 10^6
.
2. Implementation
(1) Two Pointers
思路: 利用滑动窗口的思想,维护满足条件的两个pointer start和end。注意的是每当我们在右边增加一个数时,我们引入了end - start + 1个新的subarray。比如假设我们原来有[1, 2], 当我们再右边增加3时,我们比原来多了3个subarray,分别是:
[3], [1,3], [2,3]
1
class
Solution
{
2
public
int
numSubarrayProductLessThanK
(
int
[]
nums
,
int
k
)
{
3
if
(
k
<=
1
)
{
4
return
0
;
5
}
6
7
int
prod
=
1
;
8
int
res
=
0
;
9
for
(
int
start
=
0
,
end
=
0
;
end
<
nums
.
length
;
end
++
)
{
10
prod
*=
nums
[
end
];
11
12
while
(
prod
>=
k
)
{
13
prod
/=
nums
[
start
];
14
++
start
;
15
}
16
res
+=
end
-
start
+
1
;
17
}
18
return
res
;
19
}
20
}
Copied!
3. Time & Space Complexity
Two Pointers: 时间复杂度O(n), 空间复杂度O(1)
Previous
632 Smallest Range
Next
723 Candy Crush
Last modified
2yr ago
Copy link
Contents
713. Subarray Product Less Than K
1. Question
2. Implementation
3. Time & Space Complexity