LeetCode 3404 统计特殊子序列哈希表 最简分数 倒序枚举完整题解leetcode 仓库【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode本篇题解基于 leetcode 仓库中 problems/3404.count-special-subsequences.md 展开讲解如何用「枚举中间两个索引 哈希表存最简分数 倒序枚举及时剔除失效项」的套路在 O(n² logU) 时间内统计所有满足nums[p] * nums[r] nums[q] * nums[s]且相邻下标至少间隔一个数字的长度为 4 的特殊子序列。读完本文你将掌握一类「四索引等式型计数题」的通用枚举框架并理解为什么必须使用最简分数而非实数键。题目回顾给你一个只包含正整数的数组nums。特殊子序列是一个长度为 4 的子序列用下标(p, q, r, s)表示满足p q r s且必须同时满足以下两个条件nums[p] * nums[r] nums[q] * nums[s]相邻坐标之间至少间隔一个数字即q - p 1、r - q 1、s - r 1子序列指的是从原数组中删除零个或者更多元素后剩下元素不改变顺序组成的数字序列。请你返回nums中不同特殊子序列的数目。示例 1输入nums [1,2,3,4,3,6,1] 输出1解释nums中只有一个特殊子序列(p, q, r, s) (0, 2, 4, 6)对应元素为(1, 3, 3, 1)nums[p] * nums[r] nums[0] * nums[4] 1 * 3 3nums[q] * nums[s] nums[2] * nums[6] 3 * 1 3示例 2输入nums [3,4,3,4,3,4,3,4] 输出3解释nums中共有三个特殊子序列下标 (p, q, r, s)元素等式验证(0, 2, 4, 6)(3, 3, 3, 3)3 × 3 3 × 3 9(1, 3, 5, 7)(4, 4, 4, 4)4 × 4 4 × 4 16(0, 2, 5, 7)(3, 3, 4, 4)3 × 4 3 × 4 12提示7 nums.length 10001 nums[i] 1000前置知识枚举哈希表思路从乘法等式到枚举框架题目要求枚举所有满足条件的子序列并统计数量。看到p q r s这种四个索引的约束一个经典经验是这类题目一般枚举其中一个或两个索引然后借助哈希表去找另外的索引——这与三数之和、四数之和的思路一脉相承。本题多了一层约束p和r不是连续的中间隔着q直接枚举(p, r)或(q, s)都不方便。一个常见套路是枚举中间连续的两个索引。要做到这一点只需要把等式移项nums[p] * nums[r] nums[q] * nums[s] ⟺ nums[p] / nums[q] nums[s] / nums[r]这样左侧只依赖(p, q)右侧只依赖(r, s)两个部分被彻底解耦枚举所有满足间隔约束的(p, q)把nums[p] / nums[q]记录到哈希表中枚举所有满足间隔约束的(r, s)在哈希表中查询nums[s] / nums[r]出现的次数并累加进答案。为什么必须用最简分数而不是实数nums[p] / nums[q]是实数直接用浮点数当哈希表的键会引入精度问题。因此代码上用最简分数表示a和b的最简分数其分子为a / gcd(a, b)分母为b / gcd(a, b)其中gcd为最大公约数。这样同一比值的不同表示如2/4与1/2会归一化为同一个键。算法步骤详解步骤一预处理所有合法的 (p, q) 最简分数对for p in range(len(nums) - 6): for q in range(p 2, len(nums) - 4): g gcd(nums[p], nums[q]) d[(nums[p] // g, nums[q] // g)] 1两个循环边界都是有讲究的q从p 2开始天然满足q - p 1p最多枚举到len(nums) - 7即range(len(nums) - 6)的最后一个值q最多枚举到len(nums) - 5。这是因为必须为r、s预留位置最小配置为p n - 7、q p 2 n - 5、r q 2 n - 3、s r 2 n - 1恰好覆盖数组末尾。若p或q再大就无法同时满足r - q 1与s - r 1了。步骤二倒序枚举 (r, s) 并查询哈希表for r in range(len(nums) - 3, 3, -1): # 倒着遍历 for s in range(r 2, len(nums)): g gcd(nums[r], nums[s]) ans d[(nums[s] // g, nums[r] // g)]r从len(nums) - 4递减到4s从r 2到len(nums) - 1保证s - r 1且预留了p、q的位置。注意查询键的写法d[(nums[s] // g, nums[r] // g)]即nums[s] / nums[r]的最简分数。因为由移项等式左侧(p, q)的比值要与右侧(s, r)的比值相等所以预处理时以(p, q)顺序归一化存储查询时以(s, r)顺序归一化查找二者在数值上严格对应。为什么必须倒序枚举如果(r, s)也从前往后枚举那么最开始的几个(p, q)会与(r, s)产生下标重叠无法满足p q r s的严格顺序约束。倒序枚举并配合步骤三的删除逻辑才能保证哈希表中只存在当前r位置下仍然合法的(p, q)对。步骤三及时删除即将失效的 (p, q) 对# 删掉不符合条件的 p/q q r - 2 for p in range(r - 4, -1, -1): g gcd(nums[p], nums[q]) d[(nums[p] // g, nums[q] // g)] - 1这是整个算法最精妙的一步。当r指向索引i时合法q的上界是i - 2而当循环推进到r i - 1时q i - 2的配对将不再满足r - q 1因为新间距变为1。因此在枚举完当前r的所有s之后立即把q r - 2的所有配对从哈希表中删除。p从r - 4递减到0是因为p还需满足p q - 2 r - 4。删除操作使用的是- 1而不是从字典中直接弹出因此即使计数减到 0后续查询也只贡献 0不影响结果这种写法实现更简洁也避免了在遍历中修改字典结构的复杂度。关键点这种四索引等式型题目一般枚举其中两个索引确定后借助哈希表找另外两个索引使用最简分数存储比值避免实数精度问题哈希表以(归一化分子, 归一化分母)为键倒序枚举(r, s)并在枚举过程中删除即将不符合下标间隔约束的最简分数对保证哈希表始终只包含当前合法项。代码实现语言支持Python3。from collections import Counter from math import gcd from typing import List class Solution: def numberOfSubsequences(self, nums: List[int]) - int: d Counter() # 哈希表键为 (p, q) 的最简分数对 ans 0 for p in range(len(nums) - 6): for q in range(p 2, len(nums) - 4): g gcd(nums[p], nums[q]) d[(nums[p] // g, nums[q] // g)] 1 for r in range(len(nums) - 3, 3, -1): # 倒着遍历 for s in range(r 2, len(nums)): g gcd(nums[r], nums[s]) ans d[(nums[s] // g, nums[r] // g)] # 删掉不符合条件的 p/q q r - 2 for p in range(r - 4, -1, -1): g gcd(nums[p], nums[q]) d[(nums[p] // g, nums[q] // g)] - 1 return ans原文档代码中Counter与gcd的导入被省略这里补全为可直接运行的完整版本。复杂度分析令n为数组长度U为值域。时间复杂度O(n² logU)。两个双层循环各约 O(n²) 次迭代每次迭代调用一次gcd其开销为 O(logU)其中logU来自最大公约数的辗转相除过程。空间复杂度O(n²)。最简分数对的理论上限不会超过 n²因此哈希表的空间复杂度为 O(n²)。纵深拓展最大公约数与仓库内相关题解GCD 的多种求法本题正确性的基石是「最简分数」而最简分数的计算依赖最大公约数。仓库的 最大公约数专题 对 GCD 进行了系统梳理除了本题使用的辗转相除法外还给出了另外两种思路定义法从min(a, b)向下逐个试探能否同时整除a、b。时间复杂度最坏 O(N)空间 O(1)。辗转相除法本题所用a除以b得余数c问题转化为求b与c的公约数递归直至整除。时间复杂度 O(log(max(a, b)))这也是它能支撑 O(n² logU) 总复杂度的原因。更相减损术出自《九章算术》利用gcd(a, b) gcd(a - b, b)a b。但若两数相差悬殊递归深度会明显增加最坏退化到 O(max(a, b))因此通常与辗转相除法结合使用。该专题还指出LeetCode 中虽然没有直接要求求 GCD 的题目但存在不少间接使用 GCD 的题目例如 365. 水壶问题用 BFS 求解会超时最终依赖 GCD 判定两个容量能否凑出目标水量、914. 卡牌分组 等。仓库内同样以 GCD 为核心的另一道计数题3336. 最大公约数相等的子序列数量 与本题同属「以最大公约数为纽带」的计数问题但它采用动态规划解法定义dp(i, gcd1, gcd2)表示从i开始划分seq1与seq2当前最大公约数分别为gcd1、gcd2时的方案数每个元素有三种选择放入 seq1、放入 seq2、不放状态数为 O(n·m²)其中m为值域。与本题对比阅读可以同时体会「枚举 哈希表」与「DP 状态压缩」两条截然不同的计数路径。小结3404. 统计特殊子序列的数目是一道典型的「四索引等式计数」题通过移项将乘法等式拆解为两个独立的比值再用哈希表以最简分数为键完成 O(1) 查询p、q的正向预处理与r、s的倒序枚举配合「过期即删」的维护策略巧妙地同时满足了下标顺序约束与间隔约束。掌握「枚举中间两个 哈希表存最简分数」这一套路后可迁移到三数和、四数和等一批类似的计数与查找问题中。【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
LeetCode 3404 统计特殊子序列哈希表 最简分数 倒序枚举完整题解leetcode 仓库【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode本篇题解基于 leetcode 仓库中 problems/3404.count-special-subsequences.md 展开讲解如何用「枚举中间两个索引 哈希表存最简分数 倒序枚举及时剔除失效项」的套路在 O(n² logU) 时间内统计所有满足nums[p] * nums[r] nums[q] * nums[s]且相邻下标至少间隔一个数字的长度为 4 的特殊子序列。读完本文你将掌握一类「四索引等式型计数题」的通用枚举框架并理解为什么必须使用最简分数而非实数键。题目回顾给你一个只包含正整数的数组nums。特殊子序列是一个长度为 4 的子序列用下标(p, q, r, s)表示满足p q r s且必须同时满足以下两个条件nums[p] * nums[r] nums[q] * nums[s]相邻坐标之间至少间隔一个数字即q - p 1、r - q 1、s - r 1子序列指的是从原数组中删除零个或者更多元素后剩下元素不改变顺序组成的数字序列。请你返回nums中不同特殊子序列的数目。示例 1输入nums [1,2,3,4,3,6,1] 输出1解释nums中只有一个特殊子序列(p, q, r, s) (0, 2, 4, 6)对应元素为(1, 3, 3, 1)nums[p] * nums[r] nums[0] * nums[4] 1 * 3 3nums[q] * nums[s] nums[2] * nums[6] 3 * 1 3示例 2输入nums [3,4,3,4,3,4,3,4] 输出3解释nums中共有三个特殊子序列下标 (p, q, r, s)元素等式验证(0, 2, 4, 6)(3, 3, 3, 3)3 × 3 3 × 3 9(1, 3, 5, 7)(4, 4, 4, 4)4 × 4 4 × 4 16(0, 2, 5, 7)(3, 3, 4, 4)3 × 4 3 × 4 12提示7 nums.length 10001 nums[i] 1000前置知识枚举哈希表思路从乘法等式到枚举框架题目要求枚举所有满足条件的子序列并统计数量。看到p q r s这种四个索引的约束一个经典经验是这类题目一般枚举其中一个或两个索引然后借助哈希表去找另外的索引——这与三数之和、四数之和的思路一脉相承。本题多了一层约束p和r不是连续的中间隔着q直接枚举(p, r)或(q, s)都不方便。一个常见套路是枚举中间连续的两个索引。要做到这一点只需要把等式移项nums[p] * nums[r] nums[q] * nums[s] ⟺ nums[p] / nums[q] nums[s] / nums[r]这样左侧只依赖(p, q)右侧只依赖(r, s)两个部分被彻底解耦枚举所有满足间隔约束的(p, q)把nums[p] / nums[q]记录到哈希表中枚举所有满足间隔约束的(r, s)在哈希表中查询nums[s] / nums[r]出现的次数并累加进答案。为什么必须用最简分数而不是实数nums[p] / nums[q]是实数直接用浮点数当哈希表的键会引入精度问题。因此代码上用最简分数表示a和b的最简分数其分子为a / gcd(a, b)分母为b / gcd(a, b)其中gcd为最大公约数。这样同一比值的不同表示如2/4与1/2会归一化为同一个键。算法步骤详解步骤一预处理所有合法的 (p, q) 最简分数对for p in range(len(nums) - 6): for q in range(p 2, len(nums) - 4): g gcd(nums[p], nums[q]) d[(nums[p] // g, nums[q] // g)] 1两个循环边界都是有讲究的q从p 2开始天然满足q - p 1p最多枚举到len(nums) - 7即range(len(nums) - 6)的最后一个值q最多枚举到len(nums) - 5。这是因为必须为r、s预留位置最小配置为p n - 7、q p 2 n - 5、r q 2 n - 3、s r 2 n - 1恰好覆盖数组末尾。若p或q再大就无法同时满足r - q 1与s - r 1了。步骤二倒序枚举 (r, s) 并查询哈希表for r in range(len(nums) - 3, 3, -1): # 倒着遍历 for s in range(r 2, len(nums)): g gcd(nums[r], nums[s]) ans d[(nums[s] // g, nums[r] // g)]r从len(nums) - 4递减到4s从r 2到len(nums) - 1保证s - r 1且预留了p、q的位置。注意查询键的写法d[(nums[s] // g, nums[r] // g)]即nums[s] / nums[r]的最简分数。因为由移项等式左侧(p, q)的比值要与右侧(s, r)的比值相等所以预处理时以(p, q)顺序归一化存储查询时以(s, r)顺序归一化查找二者在数值上严格对应。为什么必须倒序枚举如果(r, s)也从前往后枚举那么最开始的几个(p, q)会与(r, s)产生下标重叠无法满足p q r s的严格顺序约束。倒序枚举并配合步骤三的删除逻辑才能保证哈希表中只存在当前r位置下仍然合法的(p, q)对。步骤三及时删除即将失效的 (p, q) 对# 删掉不符合条件的 p/q q r - 2 for p in range(r - 4, -1, -1): g gcd(nums[p], nums[q]) d[(nums[p] // g, nums[q] // g)] - 1这是整个算法最精妙的一步。当r指向索引i时合法q的上界是i - 2而当循环推进到r i - 1时q i - 2的配对将不再满足r - q 1因为新间距变为1。因此在枚举完当前r的所有s之后立即把q r - 2的所有配对从哈希表中删除。p从r - 4递减到0是因为p还需满足p q - 2 r - 4。删除操作使用的是- 1而不是从字典中直接弹出因此即使计数减到 0后续查询也只贡献 0不影响结果这种写法实现更简洁也避免了在遍历中修改字典结构的复杂度。关键点这种四索引等式型题目一般枚举其中两个索引确定后借助哈希表找另外两个索引使用最简分数存储比值避免实数精度问题哈希表以(归一化分子, 归一化分母)为键倒序枚举(r, s)并在枚举过程中删除即将不符合下标间隔约束的最简分数对保证哈希表始终只包含当前合法项。代码实现语言支持Python3。from collections import Counter from math import gcd from typing import List class Solution: def numberOfSubsequences(self, nums: List[int]) - int: d Counter() # 哈希表键为 (p, q) 的最简分数对 ans 0 for p in range(len(nums) - 6): for q in range(p 2, len(nums) - 4): g gcd(nums[p], nums[q]) d[(nums[p] // g, nums[q] // g)] 1 for r in range(len(nums) - 3, 3, -1): # 倒着遍历 for s in range(r 2, len(nums)): g gcd(nums[r], nums[s]) ans d[(nums[s] // g, nums[r] // g)] # 删掉不符合条件的 p/q q r - 2 for p in range(r - 4, -1, -1): g gcd(nums[p], nums[q]) d[(nums[p] // g, nums[q] // g)] - 1 return ans原文档代码中Counter与gcd的导入被省略这里补全为可直接运行的完整版本。复杂度分析令n为数组长度U为值域。时间复杂度O(n² logU)。两个双层循环各约 O(n²) 次迭代每次迭代调用一次gcd其开销为 O(logU)其中logU来自最大公约数的辗转相除过程。空间复杂度O(n²)。最简分数对的理论上限不会超过 n²因此哈希表的空间复杂度为 O(n²)。纵深拓展最大公约数与仓库内相关题解GCD 的多种求法本题正确性的基石是「最简分数」而最简分数的计算依赖最大公约数。仓库的 最大公约数专题 对 GCD 进行了系统梳理除了本题使用的辗转相除法外还给出了另外两种思路定义法从min(a, b)向下逐个试探能否同时整除a、b。时间复杂度最坏 O(N)空间 O(1)。辗转相除法本题所用a除以b得余数c问题转化为求b与c的公约数递归直至整除。时间复杂度 O(log(max(a, b)))这也是它能支撑 O(n² logU) 总复杂度的原因。更相减损术出自《九章算术》利用gcd(a, b) gcd(a - b, b)a b。但若两数相差悬殊递归深度会明显增加最坏退化到 O(max(a, b))因此通常与辗转相除法结合使用。该专题还指出LeetCode 中虽然没有直接要求求 GCD 的题目但存在不少间接使用 GCD 的题目例如 365. 水壶问题用 BFS 求解会超时最终依赖 GCD 判定两个容量能否凑出目标水量、914. 卡牌分组 等。仓库内同样以 GCD 为核心的另一道计数题3336. 最大公约数相等的子序列数量 与本题同属「以最大公约数为纽带」的计数问题但它采用动态规划解法定义dp(i, gcd1, gcd2)表示从i开始划分seq1与seq2当前最大公约数分别为gcd1、gcd2时的方案数每个元素有三种选择放入 seq1、放入 seq2、不放状态数为 O(n·m²)其中m为值域。与本题对比阅读可以同时体会「枚举 哈希表」与「DP 状态压缩」两条截然不同的计数路径。小结3404. 统计特殊子序列的数目是一道典型的「四索引等式计数」题通过移项将乘法等式拆解为两个独立的比值再用哈希表以最简分数为键完成 O(1) 查询p、q的正向预处理与r、s的倒序枚举配合「过期即删」的维护策略巧妙地同时满足了下标顺序约束与间隔约束。掌握「枚举中间两个 哈希表存最简分数」这一套路后可迁移到三数和、四数和等一批类似的计数与查找问题中。【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
