<ruby id="bdb3f"></ruby>

    <p id="bdb3f"><cite id="bdb3f"></cite></p>

      <p id="bdb3f"><cite id="bdb3f"><th id="bdb3f"></th></cite></p><p id="bdb3f"></p>
        <p id="bdb3f"><cite id="bdb3f"></cite></p>

          <pre id="bdb3f"></pre>
          <pre id="bdb3f"><del id="bdb3f"><thead id="bdb3f"></thead></del></pre>

          <ruby id="bdb3f"><mark id="bdb3f"></mark></ruby><ruby id="bdb3f"></ruby>
          <pre id="bdb3f"><pre id="bdb3f"><mark id="bdb3f"></mark></pre></pre><output id="bdb3f"></output><p id="bdb3f"></p><p id="bdb3f"></p>

          <pre id="bdb3f"><del id="bdb3f"><progress id="bdb3f"></progress></del></pre>

                <ruby id="bdb3f"></ruby>

                ThinkChat2.0新版上線,更智能更精彩,支持會話、畫圖、視頻、閱讀、搜索等,送10W Token,即刻開啟你的AI之旅 廣告
                # 0718. 最長重復子數組 ## 題目地址(718. 最長重復子數組) <https://leetcode-cn.com/problems/maximum-length-of-repeated-subarray/> ## 題目描述 ``` <pre class="calibre18">``` 給兩個整數數組 A 和 B ,返回兩個數組中公共的、長度最長的子數組的長度。 示例 1: 輸入: 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\[i\]\[j\] 為 `以 A[i], B[j] 結尾的 xxx`。這道題就是:`以 A[i], B[j] 結尾的兩個數組中公共的、長度最長的子數組的長度`。 算法很簡單: - 雙層循環找出所有的 i, j 組合,時間復雜度 O(m?n)O(m \* n)O(m?n),其中 m 和 n 分別為 A 和 B 的 長度。 - 如果 A\[i\] == B\[j\],dp\[i\]\[j\] = dp\[i - 1\]\[j - 1\] + 1 - 否則,dp\[i\]\[j\] = 0 - 循環過程記錄最大值即可。 ## 關鍵點解析 - dp 建模套路 ## 代碼 代碼支持:Python Python Code: ``` <pre class="calibre18">``` <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span> <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">findLength</span><span class="hljs-params">(self, A, B)</span>:</span> m, n = len(A), len(B) ans = <span class="hljs-params">0</span> dp = [[<span class="hljs-params">0</span> <span class="hljs-keyword">for</span> _ <span class="hljs-keyword">in</span> range(n + <span class="hljs-params">1</span>)] <span class="hljs-keyword">for</span> _ <span class="hljs-keyword">in</span> range(m + <span class="hljs-params">1</span>)] <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(<span class="hljs-params">1</span>, m + <span class="hljs-params">1</span>): <span class="hljs-keyword">for</span> j <span class="hljs-keyword">in</span> range(<span class="hljs-params">1</span>, n + <span class="hljs-params">1</span>): <span class="hljs-keyword">if</span> A[i - <span class="hljs-params">1</span>] == B[j - <span class="hljs-params">1</span>]: dp[i][j] = dp[i - <span class="hljs-params">1</span>][j - <span class="hljs-params">1</span>] + <span class="hljs-params">1</span> ans = max(ans, dp[i][j]) <span class="hljs-keyword">return</span> ans ``` ``` **復雜度分析** - 時間復雜度:O(m?n)O(m \* n)O(m?n),其中 m 和 n 分別為 A 和 B 的 長度。 - 空間復雜度:O(m?n)O(m \* n)O(m?n),其中 m 和 n 分別為 A 和 B 的 長度。 ## 更多 - [你的衣服我扒了 - 《最長公共子序列》](https://lucifer.ren/blog/2020/07/01/LCS/) ## 擴展 二分查找也是可以的,不過并不容易想到,大家可以試試。 更多題解可以訪問我的 LeetCode 題解倉庫:<https://github.com/azl397985856/leetcode> 。 目前已經 37K star 啦。 關注公眾號力扣加加,努力用清晰直白的語言還原解題思路,并且有大量圖解,手把手教你識別套路,高效刷題。 ![](https://img.kancloud.cn/a3/63/a363818092b0356fbd67882f0389528b_900x500.jpg)
                  <ruby id="bdb3f"></ruby>

                  <p id="bdb3f"><cite id="bdb3f"></cite></p>

                    <p id="bdb3f"><cite id="bdb3f"><th id="bdb3f"></th></cite></p><p id="bdb3f"></p>
                      <p id="bdb3f"><cite id="bdb3f"></cite></p>

                        <pre id="bdb3f"></pre>
                        <pre id="bdb3f"><del id="bdb3f"><thead id="bdb3f"></thead></del></pre>

                        <ruby id="bdb3f"><mark id="bdb3f"></mark></ruby><ruby id="bdb3f"></ruby>
                        <pre id="bdb3f"><pre id="bdb3f"><mark id="bdb3f"></mark></pre></pre><output id="bdb3f"></output><p id="bdb3f"></p><p id="bdb3f"></p>

                        <pre id="bdb3f"><del id="bdb3f"><progress id="bdb3f"></progress></del></pre>

                              <ruby id="bdb3f"></ruby>

                              哎呀哎呀视频在线观看