带限制条件的最长斐波那契子序列（长度至少为3） 题目描述 给定一个严格递增的正整数数组 arr ，找出数组中最长的斐波那契式子序列的长度。斐波那契式子序列需满足：对于所有 i ≥ 2 ，有 X_i = X_{i-1} + X_{i-2} 。要求子序列长度至少为3。若不存在这样的子序列，返回0。 示例 输入： arr = [1, 3, 7, 11, 12, 14, 18] 输出： 3 解释：最长斐波那契式子序列为 [1, 11, 12] （满足 1+11=12）或 [3, 11, 14] （满足 3+11=14）等，长度均为3。 解题过程 步骤1：理解斐波那契子序列的性质 斐波那契子序列由任意两个起始元素 arr[i] 和 arr[j] （i < j）唯一确定，后续元素必须满足递推关系。由于数组严格递增，可以通过哈希表快速查找是否存在下一个所需的值。 步骤2：定义动态规划状态 定义 dp[i][j] 表示以 arr[i] 和 arr[j] 作为最后两个元素的斐波那契子序列的最大长度。 状态转移：对于一对 (i, j) ，前一个元素应为 prev = arr[j] - arr[i] 。若 prev 存在且其索引 k 满足 k < i ，则： \[ dp[ i][ j] = dp[ k][ i ] + 1 \] 若不存在这样的 k ，则初始长度为2（即仅包含 arr[i] 和 arr[j] 两个元素）。 最终答案取所有 dp[i][j] ≥ 3 中的最大值，若没有则返回0。 步骤3：初始化与查找优化 用哈希表 indexMap 存储每个值对应的索引，便于快速查找 prev 。 初始化所有 dp[i][j] = 2 （默认任意两元素可构成长度为2的序列）。 步骤4：动态规划填充顺序 外层循环遍历 j （第二个数的索引），内层循环遍历 i （第一个数的索引，且 i < j ）。 对于每对 (i, j) ： 计算 prev = arr[j] - arr[i] 。 若 prev 在哈希表中且其索引 k 满足 k < i ，则更新 dp[i][j] = dp[k][i] + 1 。 更新全局最大长度 ans = max(ans, dp[i][j]) 。 步骤5：示例推导 以 arr = [1, 3, 7, 11, 12, 14, 18] 为例： 当 (i, j) = (0, 3) （对应值1和11）： prev = 11-1=10 不存在， dp[0][3]=2 。 当 (i, j) = (3, 4) （值11和12）： prev=12-11=1 ，索引0存在且0<3，故 dp[3][4] = dp[0][3] + 1 = 3 。 最终找到多个长度为3的序列，如 [1,11,12] 、 [3,11,14] 。 步骤6：复杂度分析 时间复杂度：O(n²)，需要遍历所有 (i, j) 对。 空间复杂度：O(n²)，用于存储 dp 数组。 通过以上步骤，可系统性地找到最长斐波那契子序列。