技術文章 » LeetCode 周賽 352（2023/07/02）一場關於子陣列的專題周賽

LeetCode 周賽 352（2023/07/02）一場關於子陣列的專題周賽

2023-07-05 06:01:27

本文已收錄到 AndroidFamily，技術和職場問題，請關注公眾號 [彭旭銳] 和 [BaguTree Pro] 知識星球提問。

單週賽 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-subarrays/solutions/2327213/onde-by-dengyun-yyl3/

好棒的思維！

使用逆向思維，我們考慮每個元素 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)$ 前字尾陣列空間。

往期回顧