本文已收录到 AndroidFamily,技术和职场问题,请关注公众号 [彭旭锐] 和 [BaguTree Pro] 常识星球发问。
  • 往期回顾:LeetCode 单周赛第 350 场 · 滑动窗口与离散化模板题

单周赛 352 概览

T1. 最长奇偶子数组(Easy)

  • 标签:滑动窗口、枚举

T2. 和等于目标值的质数对(Medium)

  • 标签:质数筛、散列表、数学

T3. 不间断子数组(Medium)

  • 标签:滑动窗口、均衡树、枯燥队列

T4. 所有子数组中不均衡数字之和(Hard)

  • 标签:均衡树、散列表、前后缀合成、乘法原理


T1. 最长奇偶子数组(Easy)

https://leetcode.cn/problems/longest-even-odd-subarray-with-threshold/

题解一(滑动窗口 + 枚举子数组)

容易想到的办法是枚举每个地位开始的子数组,并计算最长奇偶子数组长度,能够失去工夫复杂度为 O(n^2) 的解法。

class Solution {    fun longestAlternatingSubarray(nums: IntArray, threshold: Int): Int {        var i = 0        var j = 0        val n = nums.size        var ret = 0        while (j < n) {            while (i < n && (nums[i] % 2 != 0 || nums[i] > threshold)) i++            if (i >= n) break            j = i + 1            while (j < n && (nums[j] % 2 != nums[j - 1] % 2 && nums[j] <= threshold)) j++            ret = Math.max(ret, j - i)            i ++        }        return ret    }}

复杂度剖析:

  • 工夫复杂度:$O(n^2)$ 最坏状况整个数组都是奇偶子数组;
  • 空间复杂度:$O(1)$ 仅应用常量级别空间。

题解二(枚举分组)

实际上,数组被宰割为若干个满足奇偶子数组的片段,最长奇偶子数组不会被其余更长的奇偶子数组所蕴含。因而,咱们不须要枚举所有地位开始的子数组,而是枚举所有片段,批改仅在于于 ++j 批改为 i = j 而已。

class Solution {    fun longestAlternatingSubarray(nums: IntArray, threshold: Int): Int {        var i = 0        var j = 0        val n = nums.size        var ret = 0        while (j < n) {            while (i < n && (nums[i] % 2 != 0 || nums[i] > threshold)) i++            if (i >= n) break            j = i + 1            while (j < n && (nums[j] % 2 != nums[j - 1] % 2 && nums[j] <= threshold)) j++            ret = Math.max(ret, j - i)            i = j // 惟一批改        }        return ret    }}

复杂度剖析:

  • 工夫复杂度:$O(n)$ i 指针和 j 指针最多挪动 n 次;
  • 空间复杂度:$O(1)$ 仅应用常量级别空间。

T2. 和等于目标值的质数对(Medium)

https://leetcode.cn/problems/prime-pairs-with-target-sum/

题解一(线性筛 + 散列表)

先预处理出数据范畴内所有质数,再应用两数之和寻找匹配项。

class Solution {    companion object {        private val U = 1000000        private val primes = generatePrime(U)        private val primeSet = primes.toHashSet()        private fun generatePrime(n : Int): LinkedList<Int> {            // 线性筛            val primes = LinkedList<Int>()            val isPrime = BooleanArray(n + 1) { true }            for (e in 2..n) {                if (isPrime[e]) {                    primes.add(e)                }                // 标记                for (prime in primes) {                    if (prime * e >= n) break                    isPrime[prime * e] = false                    if (e % prime == 0) break // 保障被最小的质因子标记                }            }            return primes        }    }    fun findPrimePairs(n: Int): List<List<Int>> {        val ret = LinkedList<List<Int>>()        for (x in primes) {            val y = n - x            // 去重            if (y < x) break            if (primeSet.contains(y)) ret.add(listOf(x, y))           }        return ret    }}

复杂度剖析:

  • 工夫复杂度:预处理工夫 $O(U)$,每次查问工夫为 $O(n)$;
  • 空间复杂度:预处理空间 $O(U)$,每次查问空间为 $O(1)$,不思考后果数组。

题解二(奇数优化)

依据奇偶数性质,如果 n 为奇数,那么当且仅当 偶数 + 奇数 = 奇数,而在所有质因子中,仅存在惟一的偶数 2。因而,当 n 为奇数时,只须要判断 n - 2 是否为质因子即可,且仅存在惟一的匹配。

class Solution {    companion object {        // 预处理 ...    }    fun findPrimePairs(n: Int): List<List<Int>> {        val ret = LinkedList<List<Int>>()        if (n % 2 == 1) {            if (primeSet.contains(n - 2)) ret.add(listOf(2, n - 2))            return ret        }        for (x in primes) {            val y = n - x            // 去重            if (y < x) break            if (primeSet.contains(y)) ret.add(listOf(x, y))           }        return ret    }}

复杂度剖析:

  • 工夫复杂度:预处理工夫 $O(U)$,每次查问工夫为 $O(n)$;
  • 空间复杂度:预处理空间 $O(U)$,每次查问空间为 $O(1)$,不思考后果数组。

T3. 不间断子数组(Medium)

https://leetcode.cn/problems/continuous-subarrays/

题解一(滑动窗口 + 暴力 · 超出工夫限度)

这道题与 1438. 相对差不超过限度的最长间断子数组 是简直雷同的,区别在于本题固定相对差至少为 2,且指标后果是计划数而不是最长不间断子数组。

与本周赛 T1 相似,咱们应用滑动窗口并维持窗口内的数据特色,从而计算满足条件的子数组计划数。同时咱们发现,每个以 nums[i] 为结尾的最长不间断子数组 [i, j],都能提供 j - i + 1 个计划,因而咱们只需要求出每段间断的不间断子数组,再累加后果。

class Solution {    fun continuousSubarrays(nums: IntArray): Long {        var i = 0        var ret = 0L        for (j in nums.indices) {            // 膨胀左指针            for (k in i until j) {                if (Math.abs(nums[k] - nums[j]) > 2) i = k + 1            }            ret += j - i + 1        }        return ret    }}

复杂度剖析:

  • 工夫复杂度:$O(n^2)$ 最坏状况下在整个数组都是不间断数组时,工夫复杂度是 $O(n^2)$;
  • 空间复杂度:$O(1)$ 仅应用常量级别空间。

题解二(滑动窗口 + 均衡树)

题解一中每次挪动右指针,都须要枚举窗口元素查看是否满足相对差至少为 2,最坏状况下工夫复杂度是 O(n^2)。为优化工夫复杂度,咱们应用有序汇合,每次仅须要查看汇合中的最小值与 nums[j] 的大小关系:

class Solution {    fun continuousSubarrays(nums: IntArray): Long {        var i = 0        var ret = 0L        val tree = TreeMap<Int, Int>()        for (j in nums.indices) {            // 膨胀左指针            while (!tree.isEmpty() && (nums[j] - tree.firstKey() > 2 || tree.lastKey() - nums[j] > 2)) {                tree[nums[i]] = tree[nums[i]]!! - 1                if (0 == tree[nums[i]]!!) tree.remove(nums[i])                i++            }            tree[nums[j]] = tree.getOrDefault(nums[j], 0) + 1            ret += j - i + 1        }        return ret    }}

复杂度剖析:

  • 工夫复杂度:$O(n)$ 每个元素最多入队一次,保护有序汇合排序的工夫复杂度是 $O(nlgn)$,因为相对差至少为 2,有序汇合中最多仅会存储 3 个键值对,排序工夫升高为常数,因而工夫复杂度是 $O(n)$;
  • 空间复杂度:$O(1)$ 有序汇合空间,理论占用空间为常量级别空间。

题解三(滑动窗口 + 双堆)

同理,咱们应用双堆也能够实现均衡树雷同的性能。

class Solution {    fun continuousSubarrays(nums: IntArray): Long {        var ret = 0L        var i = 0        val maxHeap = PriorityQueue<Int>() { i1, i2 ->            nums[i2] - nums[i1]        }        val minHeap = PriorityQueue<Int>() { i1, i2 ->            nums[i1] - nums[i2]        }        for (j in nums.indices) {            // 膨胀左指针            while (!maxHeap.isEmpty() && nums[maxHeap.peek()] - nums[j] > 2) {                maxHeap.remove(i)                minHeap.remove(i)                i++            }            while (!minHeap.isEmpty() && nums[j] - nums[minHeap.peek()] > 2) {                maxHeap.remove(i)                minHeap.remove(i)                i++            }            maxHeap.offer(j)            minHeap.offer(j)            ret += maxHeap.size            // ret += j - i + 1        }        return ret    }}

复杂度剖析:

  • 工夫复杂度:$O(n)$ 每个元素最多入堆两次,保护堆排序的工夫复杂度是 $O(nlgn)$,因为相对差至少为 2,堆中最多仅会存储 3 个元素,排序工夫升高为常数,因而工夫复杂度是 O(n);
  • 空间复杂度:$O(1)$ 双堆空间,理论占用空间为常量级别空间。

题解四(滑动窗口 + 枯燥队列)

求滑动窗口的极值问题有枯燥队列的教训解。

在有序汇合的解法中,疏忽了滑动窗口中元素的程序关系:当元素 nums[i] 前方呈现呈现更大的元素时,那么 nums[i] 不可能对滑动窗口的 x - nums[j] 的后果有奉献;同理,当 nums[i] 前方呈现更小的元素时,那么 nums[i] 不可能对滑动窗口的 nums[i] - x 的后果有奉献。

对后果没有奉献的元素,应该提前弹出数据结构(在均衡树和堆的解法中,会保留在数据结构中,从而拉低工夫复杂度)。

class Solution {    fun continuousSubarrays(nums: IntArray): Long {        var ret = 0L        var i = 0        // 从队头到队尾递加(保护滑动窗口的最大值)        val maxQueue = ArrayDeque<Int>()        // 从队头到队尾递增(保护滑动窗口的最小值)        val minQueue = ArrayDeque<Int>()        for (j in nums.indices) {            // 保护枯燥性            while (!maxQueue.isEmpty() && maxQueue.peekLast() < nums[j]) maxQueue.pollLast()            while (!minQueue.isEmpty() && minQueue.peekLast() > nums[j]) minQueue.pollLast()            maxQueue.offer(nums[j])            minQueue.offer(nums[j])            // 保护滑动窗口极值            while (maxQueue.peekFirst() - minQueue.peekFirst() > 2) {                if (nums[i] == maxQueue.peekFirst()) maxQueue.pollFirst()                if (nums[i] == minQueue.peekFirst()) minQueue.pollFirst()                i++            }            ret += j - i + 1        }        return ret    }}

复杂度剖析:

  • 工夫复杂度:$O(n)$ 在每次查看仅须要查看队尾元素,每个元素最多出队和出队两次,这是严格 $O(n)$ 的解法;
  • 空间复杂度:$O(1)$ 枯燥队列空间,理论占用空间为常量级别空间。

T4. 所有子数组中不均衡数字之和(Hard)

https://leetcode.cn/problems/sum-of-imbalance-numbers-of-all-subarrays/

题解一(枚举子数组 + 均衡树)

题目的不均衡度示意子数组排序后与前驱元素的差值大于 1 的个数(长度为 k 的子数组的最大不均衡度为 k - 1),最间接的做法是先排序再计数。咱们能够保护子数组的有序汇合,并保护插入前后的不均衡度:

  • 如果在有序汇合的首部或尾部插入,则间接调整插入后的均衡度;
  • 如果在有序汇合的两头插入,则须要减去插入前奉献的不均衡度,再减少插入后奉献的不均衡度:
class Solution {    fun sumImbalanceNumbers(nums: IntArray): Int {        var ret = 0        for (i in 0 until nums.size) {            var cnt = 0            val tree = TreeSet<Int>()            for (j in i until nums.size) {                val pivot = nums[j]                val lower = tree.floor(pivot) // 小于等于                val higher = tree.ceiling(pivot) // 大于等于                if (null != lower && null != higher && higher - lower > 1) cnt--                if (null != lower && pivot - lower > 1) cnt++                if (null != higher && higher - pivot > 1) cnt ++                tree.add(pivot)                // 子数组后果                ret += cnt            }        }        return ret    }}

复杂度剖析:

  • 工夫复杂度:$O(n·nlgn)$ 外层循环枚举 n 次,有序汇合排序工夫为 $O(nlgn)$;
  • 空间复杂度:$O(n)$ 有序汇合空间。

题解二(枚举子数组 + 散列表)

因为咱们并不需要失去排序后的数组,而是查看每个元素与前驱的关系,因而对于每个元素 nums[i],咱们只须要查看 nums[i] + 1 和 nums[i] - 1 是否存在。

枚举子数组元素 i,并保护不均衡度 cnt:

  • 如果 nums[i] 曾经存在,那么减少 nums[i] 对均衡度没有影响;
  • 如果 nums[i] 不存在,那么可能结构一个不均衡度,再察看 nums[i] + 1 和 nums[i] - 1 是否呈现过去扣除不均衡度。
class Solution {    fun sumImbalanceNumbers(nums: IntArray): Int {        var ret = 0        for (i in 0 until nums.size) {            var cnt = 0            val set = HashSet<Int>()            for (j in i until nums.size) {                val x = nums[j]                // 保护不均衡度                if (!set.contains(x)) {                    cnt++                    if (set.contains(x + 1)) cnt--                    if (set.contains(x - 1)) cnt--                    set.add(nums[j])                }                // 子数组后果                ret += cnt - 1 // 减 1 是因为最初一个元素不会结构不均衡度            }        }        return ret    }}

复杂度剖析:

  • 工夫复杂度:$O(n^2)$ 外层循环枚举 n 次,内层循环是线性工夫;
  • 空间复杂度:$O(n)$ 散列表空间。

题解三(核心扩大 + 前后缀合成 + 乘法原理)

思路参考:https://leetcode.cn/problems/sum-of-imbalance-numbers-of-all-...

好棒的思维!

应用逆向思维,咱们思考每个元素 nums[i] 可能奉献的不均衡度,以 nums[i] 为中心点向左右扩大直到遇到最近的 nums[i] - 1,应用乘法原理能够计算出 nums[i] 对多少个子数组产生贡献度。

须要思考到,如果 nums[i] 是作为子数组的最小值时,是不会产生贡献度的,所以咱们要把这部分子数组减去。然而,在应用乘法原理时咱们无奈不便地晓得 nums[i] 在子数组中排序的地位,也就无奈晓得应该减去多少有效子数组。应用整体思维,咱们先疏忽有效子数组,同时发现每个子数组中都会存在一个最小值,因而整体来看有效子数组的个数就是子数组的个数,即 N*(N+1)/2;

同时,为了优化工夫复杂度,咱们能够在第一次线性遍历中预处理出以 nums[i] 开始的后缀中最近的 nums[i] - 1 的地位。在第二次线性遍历中求出以 nums[i] 为中点的前缀中的最近 nums[i] - 1 的地位。

最初还有一个细节,思考到存在反复数的测试用例 [2,3,1,4,3],排序后 [1,2,3,3,4] 中只有最右边的 3 会奉献不均衡度。为了防止反复计算,咱们规定排序后最右边的 3 来自于以后子数组中最左边的 3,因而在预处理后缀数组时,咱们要应用 Math.min(ids[nums[i]], ids[nums[i] - 1]) 来中断遍历。

class Solution {    fun sumImbalanceNumbers(nums: IntArray): Int {        val n = nums.size        // 前缀数组和后缀数组        // ids:记录每个元素最近呈现地位        var ids = IntArray(n + 1) { n }        val prefix = IntArray(n + 1) { -1 }        val suffix = IntArray(n + 1) { n }        // 预处理后缀数组        for (i in n - 1 downTo 0) {            suffix[i] = Math.min(ids[nums[i]], ids[nums[i] - 1])            ids[nums[i]] = i        }        // 预处理前缀数组        ids = IntArray(n + 1) { -1 }        for (i in 0 until n) {            prefix[i] = ids[nums[i] - 1]            ids[nums[i]] = i        }        // 乘法原理        var ret = 0        for (i in 0 until n) {            ret += (i - prefix[i]) * (suffix[i] - i)        }        return ret - n * (n + 1) / 2    }}

在计算前缀数组时累加后果:

class Solution {    fun sumImbalanceNumbers(nums: IntArray): Int {        val n = nums.size        // 前缀数组和后缀数组        // ids:记录每个元素最近呈现地位        var ids = IntArray(n + 1) { n }        var prefix = -1        val suffix = IntArray(n + 1) { n }        // 预处理后缀数组        for (i in n - 1 downTo 0) {            suffix[i] = Math.min(ids[nums[i]], ids[nums[i] - 1])            ids[nums[i]] = i        }        // 预处理前缀数组 + 乘法原理        var ret = 0        ids = IntArray(n + 1) { -1 }        for (i in 0 until n) {            prefix = ids[nums[i] - 1]            ids[nums[i]] = i            ret += (i - prefix) * (suffix[i] - i)        }        return ret - n * (n + 1) / 2    }}

复杂度剖析:

  • 工夫复杂度:$O(n)$ 两次线性遍历;
  • 空间复杂度:$O(n)$ 前后缀数组空间。

往期回顾

  • LeetCode 单周赛第 350 场 · 滑动窗口与离散化模板题
  • LeetCode 单周赛第 348 场 · 数位 DP 模版学会了吗?
  • LeetCode 双周赛第 107 场 · 很有意思的 T2 题
  • LeetCode 双周赛第 104 场 · 流水的动静布局,铁打的结构化思考