범위에서 중복을 찾는 더 많은 메모리 효율적인 알고리즘

Question

this 질문에서 대답에는 주어진 범위에서 범위 목록의 겹침을 찾는 알고리즘이 포함되었습니다. 하지만 내 상황에서는 n^2 쌍 형식 범위로 그룹화 할 때 n 정수 목록이 있습니다. 예를 들어 array[i]과 array[j]을 정수 배열에서 취하면 (array[i]-array[j],array[i]+array[j])은 범위를 만듭니다. 그러나 제안 된 알고리즘을 구현하기 위해 솔루션은 메모리 복잡성이 O(n^2)입니다. 메모리 (메모리 측면에서)를 더욱 최적화 할 수 있습니까?

예 : 나는 더 큰 범위 (l,r)를 가지고 있고, 나는 ranges.For 예 목록의 적어도 어느 하나 (l,r) 거짓말, 지정된 정수 배열 {1,2,3} 얼마나 많은 정수 찾을 수있다. 가능한 모든 범위는 (2-1,1+2), (3-1,1+3), (3-2,3+2)입니다. (l,r)이 (2,7)이라고 가정합니다. 그런 다음 (2,5)이 하나 이상 존재하므로 4이 답입니다.

Answer 1

배열을 정렬하여 시작합니다 (아직 정렬되지 않은 경우). 고려할 가치가있는 범위는 j == i-1입니다. j < i-1의 범위는 범위 j == i-1의 엄격한 하위 집합이 항상 있다는

i=3 j=2 ==> (8-5,8+5) = (3,13) 
i=3 j=1 ==> (8-3,8+3) = (5,11) 
i=3 j=0 ==> (8-2,8+2) = (6,10) 

i=2 j=1 ==> (5-3,5+3) = (2,8) 
i=2 j=0 ==> (5-2,5+2) = (3,7) 

i=1 j=0 ==> (3-2,3+2) = (1,5) 

공지 사항, 그래서 그 : 그럼 가능한 범위는

{2,3,5,8} 

: 이해하기

이유는 다음과 같은 배열을 고려 범위를 고려할 필요가 없습니다. 따라서 O (n) 범위 만 고려하면됩니다.