算法题中的神技

神技

记录网上看到的，泛用性较强的解题神技，持续更新

前缀“乘”

713. 乘积小于 K 的子数组 - 力扣（LeetCode）

往往前缀和，当用乘法表示加和时，是会很容易爆ll的，那么，我们可以通过 \(log\) 对数将乘法转换成加法，把之转化成真正的前缀“和“。尽管，我们无法得到精确的值，但用来作为条件判断已经足够了

前缀和求解转化为

$ ps[i] = ps[i-1]+log(nums[i])$

求 \([l,r]\) 的乘积小于 \(k\) 可表示为

\(ps[m]-ps[i-1]+10^{-10}<logk\)

double 类型只能保证 \(15\) 位有效数字是精确的。为了避免计算带来的误差，相减后要加上 \(10^{-10}\)（题目中的 double 数值整数部分的数字不超过 5 个） ，从而防止不等式两边数值相等却被判定为大于的情况。