LeetCode_滑动窗口_二分搜索_中等_713.乘积小于 K 的子数组
2023-09-27 14:25:46 时间
1.题目
给你一个整数数组 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
来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/subarray-product-less-than-k
2.思路
(1)滑动窗口
思路参考本题官方题解。
(2)二分搜索
思路参考本题官方题解。
3.代码实现(Java)
//思路1————滑动窗口
class Solution {
public int numSubarrayProductLessThanK(int[] nums, int k) {
int res = 0;
int length = nums.length;
int left = 0, right = 0;
int mul = 1;
while (right < length) {
mul *= nums[right];
while (mul >= k && left <= right) {
mul /= nums[left];
//窗口左端点向右移动,即窗口变小
left++;
}
//记录以 right 为右端点且所有元素的乘积严格小于 k 的连续子数组的数目
res += right - left + 1;
right++;
}
return res;
}
}
//思路2————二分搜索
class Solution {
public int numSubarrayProductLessThanK(int[] nums, int k) {
if (k == 0) {
return 0;
}
// res 记录最终的结果
int res = 0;
int length = nums.length;
double[] logPrefix = new double[length + 1];
for (int i = 0; i < length; i++) {
logPrefix[i + 1] = logPrefix[i] + Math.log(nums[i]);
}
double logK = Math.log(k);
for (int i = 0; i < length; i++) {
int left = 0;
int right = i + 1;
int idx = i + 1;
double value = logPrefix[i + 1] - logK + 1e-10;
while (left <= right) {
int mid = left + (right - left) / 2;
if (logPrefix[mid] > value) {
idx = mid;
right = mid - 1;
} else {
left = mid + 1;
}
}
res += i + 1 - idx;
}
return res;
}
}
相关文章
- 【LeetCode-面试算法经典-Java实现】【033-Search in Rotated Sorted Array(在旋转数组中搜索)】
- LeetCode高频题70. 爬楼梯,青蛙跳台阶,暴力递归的尝试,改记忆化搜索和动态规划代码
- LeetCode | 二叉树高频面试算法题汇总【速来】
- LeetCode搜索二叉树的练习
- 110、【树与二叉树】leetcode ——450. 删除二叉搜索树中的节点:递归法+迭代法(C++版本)
- 109、【树与二叉树】leetcode ——701. 二叉搜索树中的插入操作:递归法+双指针迭代法(C++版本)
- 69、【哈希表】leetcode——202. 快乐数(C++版本)
- 【leetcode】108:将有序数组转化为二叉搜索树
- [LeetCode] 1052. Grumpy Bookstore Owner 暴躁的书店老板
- [LeetCode] 1038. Binary Search Tree to Greater Sum Tree 二叉搜索树到较大和树
- [LeetCode] 966. Vowel Spellchecker 元音拼写检查器
- [LeetCode] 888. Fair Candy Swap 公平糖果交换
- [LeetCode] Search in a Binary Search Tree 二叉搜索树中搜索
- [LeetCode] Average of Levels in Binary Tree 二叉树的层平均值
- [LeetCode] 538. Convert BST to Greater Tree 将二叉搜索树BST转为较大树
- [LeetCode] 333. Largest BST Subtree 最大的二分搜索子树
- [LeetCode] 235. Lowest Common Ancestor of a Binary Search Tree 二叉搜索树的最小共同父节点
- [LeetCode] 212. Word Search II 词语搜索之二
- [LeetCode] 79. Word Search 词语搜索
- [LeetCode] 33. Search in Rotated Sorted Array 在旋转有序数组中搜索
- [LeetCode] 89. Gray Code 格雷码
- [LeetCode] 95. Unique Binary Search Trees II 独一无二的二叉搜索树之二
- [LeetCode] Convert Sorted Array to Binary Search Tree 将有序数组转为二叉搜索树
- LeetCode将有序数组转换为二叉搜索树
- leetcode 538. Convert BST to Greater Tree 把二叉搜索树转换为累加树(简单)
- leetcode 81. Search in Rotated Sorted Array II 搜索旋转排序数组 II(中等)
- leetcode算法235.二叉搜索树的最近公共祖先
- leetcode算法94.二叉树的中序遍历