연속 배열 Leetcode

난이도 중급
자주 묻는 질문 아마존 Facebook 구글
알고리즘 배열 코딩 해싱 인터뷰 인터뷰 준비 리트코드 LeetCodeSolutions조회수 32

문제 정책

“Contiguous Array Leetcode”문제는 사용자에게 정렬 크기 n의 a []는 1과 0으로 만 구성됩니다. 찾기 가장 긴 부분 배열 여기서 1의 수는 0의 수와 같습니다.

연속 배열 Leetcode

a[ ] = {1, 0, 1, 1, 1, 0, 0}
1 to 6

설명 : 인덱스 1에서 6까지의 하위 배열을 선택하면 길이 6의 최상의 결과를 얻을 수 있습니다. 1에서 6까지의 연속 배열에는 3 개의 3과 0 개의 XNUMX이 있습니다. 여기서는 XNUMX 기반 인덱싱을 고려했습니다.

a[ ] = {1, 1}
No such subarray

접근

순진한 방법

가능한 모든 하위 배열을 생성합니다. 1의 수가 0의 수와 같은 하위 배열이 있는지 확인합니다. 하위 배열의 왼쪽과 오른쪽 경계에 두 개의 포인터 i와 j를 사용합니다. 그런 다음 0을 -0로 바꾼 후 i에서 j까지의 부분 배열 합계가 합계 = 1인지 확인합니다. 그것이 사실이라면 조건을 만족하는 하위 배열을 찾은 것입니다. 이제 답변을 업데이트합니다.

연속 배열 leetcode 문제에 대한 알고리즘

1. Initialize a binary array a[] of size n and three variables sum, max=-1, and start.
2. Traverse through the array and update sum as -1 if a[i] is 0 else 1.
3. Traverse the inner loop and add -1 in sum if a[i] is 0 else 1.
4. Check if the sum is 0 and max is less than j-i+1, update max as j-i+1 and start as i.
5. Outside the loops check if max is -1 print "No such subarray" else print starting and ending index.

암호

연속 배열 Leetcode 문제를 해결하는 C ++ 프로그램
#include <bits/stdc++.h> 
using namespace std; 
  
int subArray(int a[], int n){ 
    int sum = 0; 
    int max = -1, start; 
  
    for(int i=0; i<n-1; i++){ 
        sum = (a[i]==0) ? -1 : 1; 
  
        for(int j=i+1; j<n; j++){ 
            (a[j]==0) ? (sum+=-1) : (sum+=1); 
  
            if(sum == 0 && max < j-i+1){ 
                max = j-i+1; 
                start = i; 
            } 
        } 
    } 
    if(max == -1) 
        cout<<"No such subarray"; 
    else
        cout<<start<<" to "<<start+max-1; 
  
    return max; 
} 
  
int main(){ 
    int a[] = { 1, 0, 1, 1, 1, 0, 0 }; 
    int n = sizeof(a) / sizeof(a[0]); 
  
    subArray(a, n); 
    return 0; 
}
1 to 6
Contiguous Array Leetcode 문제를 해결하는 Java 프로그램
class LongestSubArray{
    int subArray(int a[], int n){ 
        int sum = 0; 
        int max = -1, start=0,end=0; 
        
        for(int i=0; i<n-1; i++){ 
            sum = (a[i]==0) ? -1 : 1; 
            
            for(int j=i+1; j<n; j++){ 
                if(a[j] == 0) 
                    sum += -1; 
                else
                    sum += 1;  
                
                if(sum == 0 && max < j-i+1){ 
                    max = j-i+1; 
                    start = i; 
                } 
            } 
        } 
        if(max == -1) 
            System.out.println("No such subarray");
        else
            end = start+max-1;
            System.out.println(start+" to "+end);
        
        return max; 
    } 
    public static void main(String[] args){ 
        LongestSubArray s = new LongestSubArray(); 
        int a[] = { 1, 0, 1, 1, 1, 0, 0 }; 
        int n = a.length; 
        
        s.subArray(a, n); 
    } 
}
1 to 6

복잡성 분석

시간 복잡성

여기서부터 우리는 포인터를 고정한 상태로 배열을 순회하고있었습니다. 우리는 다음과 같은 다항식 시간 복잡도를 얻었습니다.  의 위에2) 여기서 n은 주어진 배열 a []에있는 요소의 수입니다.

공간 복잡성

O (1) 일정한 여유 공간을 사용했기 때문입니다. 우리는 일정한 수의 변수 만 만들었습니다. 그러나 초기 입력 배열 이외의 배열을 사용하지 않았습니다. 그러나 입력 요소를 저장하기 위해 배열을 사용했기 때문에 프로그램 전체는 O (N) 공간 복잡성이 있습니다.

해시 맵 사용

연속 배열 leetcode 문제에 대한 알고리즘

1. Initialize a binary array a[] of size n.
2. Initialize an unordered map.
3. Traverse through the array and update the array value of the current index as -1 if current value if 0 else 1.
4. Traverse through the array and add the elements.
5. If the sum is 0, update max as i+1 and end as i.
6. Else Traverse map and update max as i - map(sum+n) and end as i if max is less than i - map(sum+n) else update map(sum+n) as i.
7. Traverse through the array and update the array value of the current index as 0 if current value is -1 else 1.
8. If the end is greater than -1 print starting and ending index.
9. Else print "No such subarray".

여기서 우리가 한 것은 합계가 0 인 가장 큰 하위 배열을 찾을 때마다 간단히 수행합니다. 우리가하는 일은 접두사 합계를 가져 와서 동일한 합계를 찾을 수있는 곳이있는 경우 맵을 체크인하는 것입니다. 그러면 맵 +1에 저장된 값에서 현재 인덱스까지의 하위 배열의 합계는 0입니다. 여기서는 (sum + n)을 키로 사용합니다. 그러나 합계를 직접 사용할 수도 있습니다. 그러나 (sum + n)을 키로 사용하면 HashMap 대신 배열을 사용할 수도 있습니다. 그러면 (sum + n)> = 0이고 배열 인덱싱이 0부터 시작하도록 보장 할 수 있기 때문입니다.

암호

연속 배열 Leetcode 문제를 해결하는 C ++ 프로그램
#include <bits/stdc++.h> 
using namespace std; 
  
int subArray(int a[], int n){ 
    
    unordered_map<int, int> hM; 
  
    int sum = 0, max = 0, end = -1; 
  
    for(int i=0; i<n; i++) 
        a[i] = (a[i] == 0) ? -1 : 1; 
  
    for(int i=0; i<n; i++){ 
        sum += a[i]; 
  
        if(sum == 0){ 
            max = i + 1; 
            end = i; 
        } 
  
        if(hM.find(sum + n) != hM.end()){ 
            if(max < i - hM[sum + n]){ 
                max = i - hM[sum + n]; 
                end = i; 
            } 
        } 
        else 
            hM[sum + n] = i; 
    } 
  
    for(int i=0; i<n; i++) 
        a[i] = (a[i] == -1) ? 0 : 1; 
        
    if(end>-1)
        cout<<end - max + 1<<" to "<<end; 
    else
        cout<<"No such subarray";
    return max; 
} 
  
int main(){ 
    int a[] = {1, 0, 1, 1, 1, 0, 0}; 
    int n = sizeof(a) / sizeof(a[0]); 
  
    subArray(a, n); 
    return 0; 
} 
1 to 6
Contiguous Array Leetcode 문제를 해결하는 Java 프로그램
import java.util.HashMap;

class LongestSubArray{
    int subArray(int a[], int n){ 
        
        HashMap<Integer, Integer> hM = new HashMap<Integer, Integer>(); 
  
        int sum = 0, max = 0, end = -1, start = 0; 
  
        for(int i=0; i<n; i++){ 
            a[i]=(a[i]==0) ? -1 : 1; 
        } 
  
        for(int i=0; i<n; i++){ 
            sum += a[i]; 
  
            if(sum == 0){ 
                max = i + 1; 
                end = i; 
            } 
  
            if(hM.containsKey(sum + n)){ 
                if(max < i - hM.get(sum + n)){ 
                    max = i - hM.get(sum + n); 
                    end = i; 
                } 
            } 
            else 
                hM.put(sum + n, i); 
        } 
  
        for(int i=0; i<n; i++) { 
            a[i] = (a[i] == -1) ? 0 : 1; 
        } 
  
        int index = end - max + 1; 
        
        if(end>-1)
            System.out.println(index + " to " + end); 
        else
            System.out.println("No such subarray"); 
        return max;  
    } 
    public static void main(String[] args){ 
        LongestSubArray s = new LongestSubArray(); 
        int a[] = { 1, 0, 1, 1, 1, 0, 0 }; 
        int n = a.length; 
        
        s.subArray(a, n); 
    } 
}
1 to 6

복잡성 분석

시간 복잡성

의 위에) 여기서 n은 주어진 배열 a []에있는 요소의 수입니다. e가 unorder_map / HashMap을 사용했기 때문에 HashMap은 O (1) 시간이 삽입 검색, 삭제를 수행 할 수 있도록 허용하기 때문에 O (N) 시간을 달성 할 수있었습니다.

공간 복잡성

의 위에) N 개의 추가 공간을 사용했기 때문입니다. HashMap 광고를 사용했기 때문에 N 요소에 대한 정보가 저장되었으므로 최악의 경우 N 요소를 가질 수 있습니다.

코멘트를 남겨

Translate »