Cinte's Leetcode Record
0%

718. 最长重复子数组

Posted on Edited on In Disqus:
Symbols count in article: 1.1k Reading time ≈ 1 mins.

718. 最长重复子数组

标准的dp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int findLength(vector<int>& nums1, vector<int>& nums2) {
        int m = nums1.size(), n = nums2.size(), ret = 0;
        vector<int> dp(n + 1);
        int tmp = 0;
        for(int i = 1; i <= m; ++i)
        {
            tmp = 0;
            for(int j = 1; j <= n; ++j)
            {
                auto t = dp[j];
                dp[j] = nums1[i - 1] == nums2[j - 1] ? tmp + 1 : 0;
                ret = max(ret, dp[j]);
                tmp = t;
            }
        }
        return ret;
    }
};
滑动窗口

分别滑动两个数组，对齐比较

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
public:
    int findLength(vector<int>& nums1, vector<int>& nums2) {
        int m = nums1.size(), n = nums2.size();
        int ret = 0;
        for(int i = 0; i < m; ++i)
        {
            int len = min(m - i, n); // 滑的最短长度
            int r = cal(nums1, nums2, i, 0, len);
            ret = max(ret, r);
        }
        for(int i = 0; i < n; ++i)
        {
            int len = min(n - i, m);
            int r = cal(nums1, nums2, 0, i, len);
            ret = max(ret, r);
        }
        return ret;
    }
private:
    int cal(vector<int>& nums1, vector<int>& nums2, int addA, int addB, int len)
    {
        int k = 0, ret = 0;
        for(int i = 0; i < len; ++i)
        {
            if(nums1[addA + i] == nums2[addB + i])
                ++k;
            else
                k = 0;
            ret = max(ret, k);
        }
        return ret;
    }
};