x + y-z - 1과 1 사이

Question

[a_1 a_2 ... a_n]은 의 목록이 될 수 있습니다.의 정수는 [1,10n]입니다. 그 외의 경우에 x,y,z의 값이 -1 <= x+y-z <= 1, 그렇지 않으면 false 인 경우 true을 반환하는 알고리즘을 제공하십시오.

무력 알고리즘 (시간 O(n^3)에, x+y-z의 가능한 모든 조합을 실행 확인. 거기에 더 효율적인 알고리즘을?

Answer 1

예,이

가. 여기 O(n) 추가 공간을 사용하는 O(n^2) 최악의 경우 알고리즘입니다.

아이디어는 가능한 모든 쌍 (트리플 대신)을 확인하고 이미 본 요소를 반복적으로 표시하고 각각의 쌍의 합계와 비교하십시오.
각 쌍에 대해 일치하는 요소가 있는지 확인하십시오 정확히 합계입니다 (,763,210) 또는 당신이 1 (x+y+1-z == 0 -> x+y-z = -1를 추가하면 얻을 수 있습니다) 또는 당신이 1 (x+y-1-z == 0 -> x + y - z == 1)

을 줄일 경우에 얻을 수있는 요소

의사 코드 : 우리가 n에서 i를 반복

mark = new boolean[10n]; //all initialized to false 
sort arr //O(nlogn) 
for each i in n,1: (reverse order) 
    for each j in 1,i-1: 
     //neglected range check, make sure it is done 
     if (mark[arr[i]+arr[j]] || mark[arr[i]+arr[j]+1] || mark[arr[i]+arr[j]-1]): 
      return true 
     mark[arr[i]] = true 
return false 

주 1, z > x 및 z > y 때문에 - 그것은

정확성 증거가 있다면 우리가 목록에 이미있는 요소와 모든 쌍을 확인하고 있는지 확인하려면 :
해결책이있는 경우 x+y-z = 0 - 다음은 z > x 및 z > y (모든 요소는 양의 고유 한 정수입니다).
일반성을 잃지 않고 x > y으로 가정합니다. 따라서 외부 루프에 arr[i]=x을 반복 할 때 과 같은 일부 j<i이 있습니다. 또한 z>x - mark[z] == true 이후로 이전에 반복 할 때 표시했습니다.
따라서 알고리즘은 mark[arr[x] + arr[y]] == true이고 수율은 true입니다.
+-1 사례의 경우 비슷한 증거입니다.

알고리즘이 true이면 조건 ​​중 하나가 참임을 발견했습니다. mark[arr[i] + arr[j]]이라고 가정합시다 (다른 경우의 증명은 유사합니다).
그래서 우리는 mark[arr[i] + arr[j]] == true을 발견했습니다. 따라서 z = arr[i] + arr[j]과 같은 일부 요소가 z이고이 경우 알고리즘이 올바르므로이를 삽입했습니다.