企业官网建设流程全解析

1. 力扣周赛179场第三题解析

上周参加了力扣第179场周赛，第三题让我印象深刻。这道题考察了动态规划与贪心算法的结合应用，属于中等偏上难度。作为每周坚持刷题的选手，我想分享一下这道题的解题思路和优化过程。

1.1 题目重述

题目给定一个整数数组nums和整数k，要求找到数组中的"好子序列"数量。好子序列定义为：子序列中任意两个相邻元素的绝对差不超过k。由于结果可能很大，需要对10^9+7取模。

示例： 输入：nums = [2,4,6], k = 2 输出：3 解释：所有好子序列为[2], [4], [6]

1.2 题目分析

这道题有几个关键点需要注意：

1. 子序列不同于子数组，不要求连续
2. 相邻元素的绝对差限制是核心约束条件
3. 需要考虑空子序列的情况（根据题目要求可能不计入）

经过分析，这道题需要计算所有满足条件的子序列数量，暴力的解法显然不可行（时间复杂度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)，对于n=1e5的数据会超时。我们需要优化查找过程：

1. 排序数组：先对数组排序，这样对于nums[i]，满足条件的nums[j]一定在一个连续的区间内
2. 滑动窗口：维护一个滑动窗口，保证窗口内的元素与当前元素的差值不超过k
3. 前缀和：使用前缀和数组快速计算区间内的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[i+1] = (prefix[i] + dp[i]) % MOD

3.3 结果计算

最终结果是所有dp[i]的和（如果题目要求包含空子序列则再加1）：

result = sum(dp) % MOD # 如果允许空子序列： # result = (1 + sum(dp)) % MOD

4. 边界条件与注意事项

4.1 特殊输入处理

• 空数组：直接返回0或1（根据是否允许空子序列）
• k=0：只有单个元素的子序列满足条件
• 所有元素相同：所有子序列都满足条件

4.2 模运算细节

由于结果可能很大，需要注意：

1. 每次加法后都要取模
2. 前缀和做减法时可能产生负数，需要加MOD再取模
3. 最终结果要再次取模

4.3 性能优化

• 使用双指针维护滑动窗口比二分查找更高效
• 前缀和数组可以优化为变量，节省空间
• 对于Python，使用内置函数可能比手动循环更快

5. 类似题目推荐

掌握这类子序列计数问题后，可以尝试以下力扣题目：

• 1521. 找到最接近目标值的子序列和
• 1713. 得到子序列的最少操作次数
• 1911. 最大子序列交替和

这类题目通常需要结合排序、动态规划和滑动窗口等技术，是面试中的高频考点。

6. 个人刷题心得

在解决这类问题时，我总结了几个关键点：

1. 先明确子序列与子数组的区别
2. 排序往往是优化的第一步
3. 动态规划状态定义要准确
4. 前缀和可以优化区间查询
5. 双指针维护滑动窗口是常见技巧

这道题在周赛中的通过率不高，主要是因为需要综合运用多种技巧。建议平时多练习类似题目，比赛时才能快速识别题型并套用解法。