頭腦風暴：最長重複子數組

題目

給兩個整數數組 A 和 B ，傳回兩個數組中公共的、長度最長的子數組的長度。

示例：

輸入： A: [1,2,3,2,1] B: [3,2,1,4,7] 輸出：3 解釋： 長度最長的公共子數組是 [3, 2, 1] 。

提示：

• 1 <= len(A), len(B) <= 1000
• 0 <= A[i], B[i] < 100

解題思路

根據題意，本題可以使用動态規劃的方式來求解。

第一步，确定dp數組以及下标的含義：

dp[i][j] ：以下标 i - 1 為結尾的 A，和以下标 j - 1 為結尾的 B，最長重複子數組長度為 dp[i][j]。

第二步，确定遞推公式：

根據 dp[i][j] 的定義，dp[i][j] 的狀态隻能由 dp[i - 1][j - 1] 推導出來。

是以，當 A[i - 1] 和B[j - 1]相等的時候，dp[i][j] = dp[i - 1][j - 1] + 1;

第三步，dp數組初始化：

為了友善遞歸公式 dp[i][j] = dp[i - 1][j - 1] + 1，是以 dp[i][0] 和 dp[0][j] 初始化為0。

第四步，确定周遊順序：

外層for循環周遊A，内層for循環周遊B。

代碼實作

class Solution {
    public int findLength(int[] nums1, int[] nums2) {
        int result = 0;
        int[][] dp = new int[nums1.length + 1][nums2.length + 1];

        for (int i = 1; i < nums1.length + 1; i++) {
            for (int j = 1; j < nums2.length + 1; j++) {
                if (nums1[i - 1] == nums2[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                    result = Math.max(result, dp[i][j]);
                }
            }
        }

        return      

最後

• 時間複雜度：O(n × m)，n 為 A 長度，m 為 B 長度。
• 空間複雜度：O(n × m)。

我是傑少，如果您覺的我寫的不錯，那請給我 點贊+評論+收藏 後再走哦！

1. 閱讀完記得給我點個贊哦，有👍 有動力
2. 關注公衆号---HelloWorld傑少，第一時間推送新姿勢