정렬되지 않은 배열에서 값 찾기

Question

배열에서 두 숫자의 합계를 모두 찾아야합니다. 그것이 같으면 인쇄하십시오. 이 문제에 대한 선형 해결책은 O (N^2) 복잡도입니다. 정렬 및 이진 비교를 생각했습니다. 복잡도는 여전히 (NlogN + N)

문제는 모든 조합을 찾아야한다는 것입니다.

이 문제의 선형 해결책 예 :

//Linear search, find all the combinations 
Find(int a[], int Target) 
    { 
     for(i=0; i<arr_size; i++) 
      for(j=0; j<arr_size; j++) 
       if((a[i]+a[j]) == Target) 
        cout<<a[i]<<a[j] 
    } 

추가로 복잡성을 줄일 수있는 방법이 있습니까?

덕분에, 전문가

Answer 1

는 먼저 모든 불가능한를 필터링 할 수 있습니다. 이는 배열을 통해 두 번의 반복 만 필요하며 세트를 대폭 줄일 수 있습니다. 그렇지 않다면 2 번의 반복을 잃어버린 것입니다.

우선, 가장 적은 숫자를 찾아서 모든 값> (목표 - 최소 숫자)를 필터링 할 수 있습니다.

Answer 2

는 약간 성능

private static void find(int[] a, int target) { 

    for (int i = 0; i < a.length; i++) { 
     if (a[i] == target) { 
      System.out.println("result found"); 
      break; 
     } 
     if (a[i] > target) { 
      break; 
     } 
     for (int j = 0; j < a.length; j++) { 
      if ((i != j && (a[i] + a[j]) == target)) { 
       System.out.println("result found"); 
      } 
     } 
    } 
}