⭐️ 本文已收录到 AndroidFamily，技能和职场问题，请关注公众号 [彭旭锐] 和 [BaguTree Pro] 知识星球提问。

学习数据结构与算法的关键在于把握问题背面的算法思想结构，你的考虑越抽象，它能覆盖的问题域就越广，理解难度也更杂乱。在这个专栏里，小彭与你分享每场 LeetCode 周赛的解题报告，一同体会上分之旅。

本文是 LeetCode 上分之旅系列的第 30 篇文章，往期回忆请移步到文章末尾~

T1.最长奇偶子数组（Easy）

T2.和等于方针值的质数对（Medium）

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

T3.不间断子数组（Medium）

  • 标签：滑动窗口、平衡树、单调行列

T4.一切子数组中不平衡数字之和（Hard）

  • 标签：平衡树、散列表、前后缀分解、乘法原理

LeetCode 周赛 352（2023/07/02）一场关于子数组的专题周赛

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(n2)O(n^2) 最坏状况整个数组都是奇偶子数组；
  • 空间杂乱度：O(1)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)O(n) i 指针和 j 指针最多移动 n 次；
  • 空间杂乱度：O(1)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(U)，每次查询时刻为 O(n)O(n)；
  • 空间杂乱度：预处理空间 O(U)O(U)，每次查询空间为 O(1)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(U)，每次查询时刻为 O(n)O(n)；
  • 空间杂乱度：预处理空间 O(U)O(U)，每次查询空间为 O(1)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(n2)O(n^2) 最坏状况下在整个数组都是不间断数组时，时刻杂乱度是 O(n2)O(n^2)；
  • 空间杂乱度：O(1)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(n) 每个元素最多入队一次，保护有序调集排序的时刻杂乱度是 O(nlgn)O(nlgn)，因为绝对差至多为 2，有序调集中最多仅会存储 3 个键值对，排序时刻下降为常数，因而时刻杂乱度是 O(n)O(n)；
  • 空间杂乱度：O(1)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(n) 每个元素最多入堆两次，保护堆排序的时刻杂乱度是 O(nlgn)O(nlgn)，因为绝对差至多为 2，堆中最多仅会存储 3 个元素，排序时刻下降为常数，因而时刻杂乱度是 O(n)；
  • 空间杂乱度：O(1)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(n)O(n) 的解法；
  • 空间杂乱度：O(1)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)O(nnlgn) 外层循环枚举 n 次，有序调集排序时刻为 O(nlgn)O(nlgn)；
  • 空间杂乱度：O(n)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(n2)O(n^2) 外层循环枚举 n 次，内层循环是线性时刻；
  • 空间杂乱度：O(n)O(n) 散列表空间。

题解三（中心扩展 + 前后缀分解 + 乘法原理）

思路参阅：leetcode.cn/problems/su…

好棒的思想！

运用逆向思想，咱们考虑每个元素 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) 两次线性遍历；
  • 空间杂乱度：O(n)O(n) 前后缀数组空间。

引荐阅览

LeetCode 上分之旅系列往期回忆：

  • LeetCode 单周赛第 350 场 滑动窗口与离散化模板题

  • LeetCode 单周赛第 348 场 数位 DP 模版学会了吗？

  • LeetCode 双周赛第 107 场 很有意思的 T2 题

  • LeetCode 双周赛第 104 场 流水的动态规划，铁打的结构化考虑

⭐️ 永远相信美好的事情行将产生，欢迎参加小彭的 Android 交流社群~

LeetCode 周赛 352（2023/07/02）一场关于子数组的专题周赛