算法沉淀——动态规划之子数组、子串系列（下）（leetcode真题剖析）

算法沉淀——动态规划之子数组、子串系列

• 01.等差数列划分
• 02.最长湍流子数组
• 03.单词拆分
• 04.���绕字符串中唯一的子字符串

  01.等差数列划分

  题目链接：https://leetcode.cn/problems/arithmetic-slices/

  如果一个数列 至少有三个元素 ，并且任意两个相邻元素之差相同，则称该数列为等差数列。

  • 例如，[1,3,5,7,9]、[7,7,7,7] 和 [3,-1,-5,-9] 都是等差数列。

    给你一个整数数组 nums ，返回数组 nums 中所有为等差数组的 子数组 个数。

    子数组 是数组中的一个连续序列。

    示例 1：

    输入：nums = [1,2,3,4]输出：3解释：nums 中有三个子等差数组：[1, 2, 3]、[2, 3, 4] 和 [1,2,3,4] 自身。

    示例 2：

    输入：nums = [1]输出：0

    提示：

    • 1 public: int numberOfArithmeticSlices(vector int n=nums.size(); vector dp[i]=nums[i]-nums[i-1]==nums[i-1]-nums[i-2]?dp[i-1]+1:0; sum+=dp[i]; } return sum; }};public: int maxTurbulenceSize(vector int n=arr.size(); vector if(arr[i-1]public: bool wordBreak(string s, vector unordered_set for(int j=i;j=1;j--){ if(dp[j-1]&&hash.count(s.substr(j,i-j+1))){ dp[i]=true; break; } } } return dp[n]; }};public: int findSubstringInWraproundString(string s) { int n=s.size(); vector0}; for(int i=0;i