最長(zhǎng)重復(fù)子數(shù)組 findLength

默認(rèn)格式：

class Solution {
    public int findLength(int[] A, int[] B) {
    }
}

解題思路：

1，暴力算法

遍歷數(shù)組1中的每一個(gè)元素

用這個(gè)元素和數(shù)組2的每一個(gè)元素對(duì)比，如果相同

循環(huán)讀取兩個(gè)數(shù)組的下一個(gè)元素，直到不相同為止

這個(gè)算法太復(fù)雜，就不做實(shí)現(xiàn)了。

2，使用哈希表+鏈表

遍歷一遍數(shù)組1，將其每個(gè)元素出現(xiàn)的位置存入到一個(gè)List中，然后存入hashmap中。

遍歷數(shù)組2，每個(gè)元素在哈希表中是否存在，如果存在，遍歷這個(gè)List中的所有位置，對(duì)這些位置進(jìn)行測(cè)試，找出最大長(zhǎng)度

寫的時(shí)候已經(jīng)發(fā)現(xiàn)了，用哈希表來存并沒有減少核心部分的時(shí)間，時(shí)間復(fù)雜度依然很高。

    public int findLength(int[] A, int[] B) {
        int max=0;
        //構(gòu)建一個(gè)HashMap來存地址
        HashMap<Integer, List<Integer>> map=new HashMap<>();
        for (int i=0;i<A.length;i++){
            if (map.get(A[i])==null){
                List<Integer> list=new LinkedList<>();
                list.add(i);
                map.put(A[i],list);
            }else {
                map.get(A[i]).add(i);
            }
        }
        for (int i=0;i<B.length;i++){
            //如果元素在數(shù)組A中存在
            if (map.get(B[i])!=null){
                //遍歷原數(shù)組中對(duì)應(yīng)的每一個(gè)位置
                for(int index:map.get(B[i])){
                    int a=index,b=i;
                    for (;a<A.length&&b<B.length&&A[a]==B[b];a++,b++){
                    }
                    max=Integer.max(max,b-i);
                }
            }
        }
        return max;
    }

優(yōu)化1：（失?。?/h3>

這個(gè)HashMap可以使用數(shù)組來代替，因?yàn)樗锩娴闹挡粫?huì)超過100，我們可以對(duì)其進(jìn)行控制，用數(shù)組下標(biāo)來代替HashMap的鍵的功能。

    public int findLength(int[] A, int[] B) {
        int max=0;
        //使用數(shù)組來存
//        HashMap<Integer, List<Integer>> map=new HashMap<>();
        List<Integer>[] lists=new ArrayList[100];
        for (int i=0;i<A.length;i++){
            if (lists[A[i]]==null){
                List<Integer> list=new ArrayList<>();
                list.add(i);
                lists[A[i]]=list;
            }else {
                lists[A[i]].add(i);
            }
        }
        for (int i=0;i<B.length;i++){
            //如果元素在數(shù)組A中存在
            if (lists[B[i]]!=null){
                //遍歷原數(shù)組中對(duì)應(yīng)的每一個(gè)位置
                for(int index:lists[B[i]]){
                    int a=index,b=i;
                    for (;a<A.length&&b<B.length&&A[a]==B[b];a++,b++){
                    }
                    max=Integer.max(max,b-i);
                }
            }
        }
        return max;
    }

優(yōu)化2：

還是數(shù)據(jù)結(jié)構(gòu)上的優(yōu)化，我們可以使用Set來代替List，這樣可以節(jié)省一些時(shí)間

優(yōu)化到這我覺得應(yīng)該是我做題的方向錯(cuò)了，應(yīng)該有一個(gè)巧妙的方法能夠解決這個(gè)問題但是我目前沒有想到，看看官方的解答吧。

官方的解題方法有多種，我這里就選擇最巧妙的那一個(gè)方式：動(dòng)態(tài)規(guī)劃。

動(dòng)態(tài)規(guī)劃的題目之前做過很多，但是對(duì)這個(gè)概念的理解還不夠深刻，還需要多多練習(xí)。

動(dòng)態(tài)規(guī)劃的核心思想就是，一邊計(jì)算一邊記錄，并且得到的結(jié)果會(huì)累計(jì)，最后我們累計(jì)的結(jié)果就是我們需要的值。

在這道題中，我們?nèi)〕鰯?shù)組A中的一個(gè)元素，和B中每個(gè)元素比較一遍，如果相等，這能證明什么，這就證明，如果A中這個(gè)元素的前一個(gè)和B中當(dāng)前元素的前一個(gè)相等，此時(shí)這個(gè)連續(xù)的長(zhǎng)度就+1。

用這個(gè)結(jié)論，我們可以遍歷兩個(gè)數(shù)組，構(gòu)建一個(gè)a*b的二維數(shù)組，假設(shè)A種當(dāng)前元素地址是a1，B中當(dāng)前元素的地址是b1，那么當(dāng)前的長(zhǎng)度可以加上(a1-1,b1-1)這個(gè)位置的元素的值。

雖然實(shí)現(xiàn)了，但不是最優(yōu)的辦法，官方給出的最優(yōu)算法有一些復(fù)雜，沒能看懂

public int findLength(int[] A, int[] B) {
    int[][] map=new int[A.length][B.length];
    int max=0;
    for (int i=0;i<A.length;i++){
        for (int j=0;j<B.length;j++){
            if (A[i]==B[j]){
                if (i-1<0||j-1<0)
                    map[i][j]=1;
                else
                    map[i][j]=map[i-1][j-1]+1;
                max=Integer.max(max,map[i][j] );
            }
        }
    }
    return max;
}

到此這篇關(guān)于最長(zhǎng)重復(fù)子數(shù)組 findLength示例詳解的文章就介紹到這了,更多相關(guān)最長(zhǎng)重復(fù)子數(shù)組 findLength內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！