1. 力扣周赛179场第三题解析上周参加了力扣第179场周赛第三题让我印象深刻。这道题考察了动态规划与贪心算法的结合应用属于中等偏上难度。作为每周坚持刷题的选手我想分享一下这道题的解题思路和优化过程。1.1 题目重述题目给定一个整数数组nums和整数k要求找到数组中的好子序列数量。好子序列定义为子序列中任意两个相邻元素的绝对差不超过k。由于结果可能很大需要对10^97取模。示例 输入nums [2,4,6], k 2 输出3 解释所有好子序列为[2], [4], [6]1.2 题目分析这道题有几个关键点需要注意子序列不同于子数组不要求连续相邻元素的绝对差限制是核心约束条件需要考虑空子序列的情况根据题目要求可能不计入经过分析这道题需要计算所有满足条件的子序列数量暴力的解法显然不可行时间复杂度O(2^n)必须寻找更优解。2. 解题思路与算法选择2.1 动态规划解法最直接的思路是使用动态规划。定义dp[i]表示以nums[i]结尾的好子序列数量。对于每个元素nums[i]我们需要找到前面所有满足|nums[i]-nums[j]|≤k的元素nums[j]将它们的dp值累加。状态转移方程 dp[i] 1 Σdp[j] (对于所有j i且|nums[i]-nums[j]|≤k)最终结果是所有dp[i]的和如果允许空子序列则再加1。2.2 优化思路直接实现上述DP的时间复杂度是O(n^2)对于n1e5的数据会超时。我们需要优化查找过程排序数组先对数组排序这样对于nums[i]满足条件的nums[j]一定在一个连续的区间内滑动窗口维护一个滑动窗口保证窗口内的元素与当前元素的差值不超过k前缀和使用前缀和数组快速计算区间内的dp值之和这样可以将时间复杂度优化到O(nlogn)排序耗时O(n)DP过程。3. 代码实现与细节处理3.1 排序预处理首先对数组排序这样相邻元素的差值更容易控制nums.sort()3.2 动态规划实现使用dp数组记录以每个元素结尾的子序列数prefix数组记录前缀和MOD 10**9 7 n len(nums) dp [1] * n # 每个元素本身就是一个子序列 prefix [0] * (n 1) prefix[1] dp[0] left 0 for i in range(1, n): # 移动左指针找到满足nums[i]-nums[left]k的最小left while left i and nums[i] - nums[left] k: left 1 # 计算区间和 dp[i] (1 prefix[i] - prefix[left]) % MOD # 更新前缀和 prefix[i1] (prefix[i] dp[i]) % MOD3.3 结果计算最终结果是所有dp[i]的和如果题目要求包含空子序列则再加1result sum(dp) % MOD # 如果允许空子序列 # result (1 sum(dp)) % MOD4. 边界条件与注意事项4.1 特殊输入处理空数组直接返回0或1根据是否允许空子序列k0只有单个元素的子序列满足条件所有元素相同所有子序列都满足条件4.2 模运算细节由于结果可能很大需要注意每次加法后都要取模前缀和做减法时可能产生负数需要加MOD再取模最终结果要再次取模4.3 性能优化使用双指针维护滑动窗口比二分查找更高效前缀和数组可以优化为变量节省空间对于Python使用内置函数可能比手动循环更快5. 类似题目推荐掌握这类子序列计数问题后可以尝试以下力扣题目找到最接近目标值的子序列和得到子序列的最少操作次数最大子序列交替和这类题目通常需要结合排序、动态规划和滑动窗口等技术是面试中的高频考点。6. 个人刷题心得在解决这类问题时我总结了几个关键点先明确子序列与子数组的区别排序往往是优化的第一步动态规划状态定义要准确前缀和可以优化区间查询双指针维护滑动窗口是常见技巧这道题在周赛中的通过率不高主要是因为需要综合运用多种技巧。建议平时多练习类似题目比赛时才能快速识别题型并套用解法。