传送门 思路1： d p dp dp，因为数据很小都只有 1000 1000 1000，很显然类比 L C S LCS LCS可以令 d p [ i ] [ j ] dp[i][j] dp[i][j]以
a [ i ] , b [ j ] a[i],b[j] a[i],b[j]结尾的最大匹配长度。
有状态转移方程： i f ( a [ i − 1 ] = = b [ j − 1 ] ) d p [ i ] [ j ] = m a x ( d p [ i ] [ j ] , d p [ i − 1 ] [ j − 1 ] + 1 ) if(a[i-1]==b[j-1])\quad dp[i][j]=max(dp[i][j],dp[i-1][j-1]+1) if(a[i−1]==b[j−1])dp[i][j]=max(dp[i][j],dp[i−1][j−1]+1)
时间复杂度 : O ( n m ) O(nm) O(nm) 空间复杂度 : O ( n m ) O(nm) O(nm)
class Solution { public: int findLength(vector<int>& a, vector<int>& b) { int la=a.size(),lb=b.size(); vector<vector<int> >dp(1005,vector<int>(1005,0)); int ans=0; for(int i=1;i<=la;i++) for(int j=1;j<=lb;j++) { if(a[i-1]==b[j-1]) dp[i][j]=max(dp[i][j],dp[i-1][j-1]+1); if(dp[i][j]>ans) ans=dp[i][j]; } return ans; } };思路2：滑动窗口，让数组 a a a不动，数组 b b b左右移动匹配，显然我们可以枚举数组 b b b的开始位置： p o s ∈ [ 1 − s i z e b , s i z e a − 1 ] pos\in[1-size_b,size_a-1] pos∈[1−sizeb,sizea−1]
然后对 a [ i ] , b [ i − p o s ] a[i],b[i-pos] a[i],b[i−pos]匹配，更新答案即可。
时间复杂度： O ( ( n + m ) × m i n ( n , m ) ) O((n+m)\times min(n,m)) O((n+m)×min(n,m)) 空间复杂度： O ( 1 ) O(1) O(1)
class Solution { public: int findLength(vector<int>& a, vector<int>& b) { int m=a.size(),n=b.size(); int ans=0,cnt=0,mx=0; for(int move=1-n;move<=m-1;move++){ mx=cnt=0; for(int i=max(0,move);i<min(m,n+move);i++) { if(a[i]==b[i-move]) cnt++; else { mx=max(cnt,mx); cnt=0; } } mx=max(mx,cnt); ans=max(ans,mx); } return ans; } };思路3：哈希+二分优化，不是很熟就不写了，待更。
