O(1) space solution using two pointers


  • 0
    O
        public int findLength(int[] A, int[] B) {
            int i=0, j=0, maxLeng=0;  
            while (j<A.length){
                while (j<A.length && isSub(A, i, j+1, B)){
                    j++; 
                } 
                maxLeng = Math.max(maxLeng, j-i); 
                j++;
                while (i<j && !isSub(A, i, j, B)){
                    i++; 
                } 
            }
            return maxLeng; 
        }
        public boolean isSub(int[] A, int s, int e, int[] B){
            if (s>=e) return true; 
            if (e>A.length) e=A.length; 
            for (int i=0; i<=B.length-e+s; i++){
                int j=s; 
                for (; j<e; j++){
                    if (A[j]!=B[i+j-s]) break; 
                }
                if (j==e) return true; 
            }
            return false; 
        }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.