电子商务网站建设与推广/营销宣传方案

前言

题目：718. 最长重复子数组

参考题解：最长重复子数组-代码随想录、最长重复子数组-力扣官方题解

提交代码

暴力解

求两个序列，最长重复长度。暴力解，必然可以，但会超时。

具体思路见代码实现。实现如下。

#include <vector>
#include <iostream>
using namespace std;class Solution {
public:int findLength(vector<int>& nums1, vector<int>& nums2) {// 暴力解// 最长连续重复序列 == nums1[i:] nums2[j:]的最长连续前缀int result = 0;for(int i=0; i<nums1.size(); i++){for(int j=0; j<nums2.size(); j++){int tmp = 0;int ii = i;int jj = j;while(ii<nums1.size() && jj<nums2.size() && nums1[ii] == nums2[jj]){tmp++;ii++;jj++;}result = max(result,tmp);}}return result;}
};int main(void){vector<int> nums1 = {0,0,0,0,0,0,1,0,0,0};vector<int> nums2 = {0,0,0,0,0,0,0,1,0,0};Solution s;cout<<s.findLength(nums1,nums2)<<endl;
}

动态规划

下面代码实现和图片，来自参考题解。

class Solution {
public:int findLength(vector<int>& nums1, vector<int>& nums2) {// 动态规划// 如果nums1[i]和nums2[j]位置的元素相同dp[i][j] = dp[i-1][j-1] + 1; 前一个位置相同，将dp[i-1][j-1]累加过来；前一个位置不相同，dp[i-1][j-1]位零int result = 0;vector<vector<int>> dp(nums1.size()+1,vector<int>(nums2.size()+1,0));for(int i=1; i<=nums1.size(); i++){for(int j=1; j<=nums2.size(); j++){if(nums1[i-1] == nums2[j-1])dp[i][j] = dp[i-1][j-1] + 1;result = max(result,dp[i][j]);}   }return result;}
};