题解 | #最长公共子数组#

最长公共子数组

http://www.nowcoder.com/practice/6032826d387c4a10ad3690cce5fdb015

最长公共子数组

题意

给定两个子数组，求最长公共子数组的长度

方法

循环对比(TLE)

分析

公共子数组的性质是连续的一段

换句话说，从A的某个位置i开始，从B的某个位置j开始，长度为len的一段相等

那么问题可以变为，先分别选取起始位置，再进行比较，并记录最大的相等长度

代码

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param A int整型vector 
     * @param B int整型vector 
     * @return int整型
     */
    int longestCommonSubarry(vector<int>& A, vector<int>& B) {
        int ans = 0;
        for(int i = 0;i<A.size();i++){ // 枚举A中开始的位置
            for(int j = 0;j<B.size();j++){ //  枚举B开始的位置
                for(int l = 0;i+l<A.size() && j+l < B.size();l++){ // 按位对比
                    if(A[i+l] == B[j+l]) ans = max(ans,l+1);
                    else break;
                }
            }
        }
        return ans;
    }
};

复杂度分析

空间复杂度: 使用了常数个额外变量，空间复杂度为 $O (1)$

时间复杂度: 对于最里层的比较最坏情况是完全遍历，所以总时间复杂度为 $O (n^{3})$

优化枚举过程

分析

上面的搜索过程中，是每次选择两个字符串比较的起始位置进行比较的, 例如A+i开始和B+j开始

然而在后面的比较过程中，又会选取以A+i+1开始和B+j+1开始作为起始位置进行比较

这两次不同起始位置选取,都会将A[i+k] 与 B[j+k]比较,也就是有不少的位置发生重复比较了

考虑通过一个办法减少这个重复的比较

注意到分别选取字符串起始位置后,B与A对应比较的位置下标差为定值j-i

而 (A+i开始和B+j开始) 与 (A+i+1开始和B+j+1开始)这两个比较方案中,这个定值相等,都是j-i

设偏移量 $o f f s e t =$ B的起始位置 - A的起始位置

所以把循环枚举头部，改为循环枚举偏移量 $o f f s e t$

样例

以样例数据

[1,2],[1,2]

为例

alt

代码

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param A int整型vector 
     * @param B int整型vector 
     * @return int整型
     */
    int longestCommonSubarry(vector<int>& A, vector<int>& B) {
        int ans = 0;
        for(int offset = 1-(int)A.size();offset < (int)B.size();offset++){ // 偏移量 注意size是无符号的需要转换
            int cur = 0; // 当前相等的长度
            for(int i = 0;i < A.size();i++){ // A的位置
                int j = i + offset; // B的位置
                if(j < 0)continue;
                if(j >= B.size())break;
                cur = A[i] == B[j] ? cur + 1 : 0; // 相等则长度+1，不等则长度为0
                ans = max(ans, cur); // 最大值
            }
        }
        return ans;
    }
};