루비 배열에 값 저장을위한 메모 사용하기

Question

짧은 배열의 경우 다음 함수가 잘 작동합니다. 그것은 whe 합이 주어진 정수와 같은 첫 번째 배열 쌍을 반환한다고 가정합니다. 그러나 배열의 길이가 1 천만 개 이상인 경우 요청이 시간 초과됩니다. 왜냐하면 (내가 생각하기에) 첫 번째 줄에 만드는 변수에 수천 개의 값을 저장하기 때문입니다. 나는 memoization (|| =)을 사용해야 만하지만 그것을 어떻게 사용해야할지 모른다.

array1 = [1,2,3,4,5,6,7] 
number = 3 
array2 = [1,2,3.....n] # millions of elements 
combos = array1.combination(2).to_a 
(combos.select { |x,y| x + y == number }).sort.first 

은 내가 전체 목록을 가서 true를 돌려 첫 번째 쌍에서 중지하지 않는 선택 사용하고, 그들을 정렬 모든 가능한 쌍을 수집해야합니다.

Answer 1

def find_smallest(arr, nbr) 
    first, *rest = arr.sort 
    until rest.empty? 
    matching = rest.bsearch { |n| n == nbr - first } 
    return [first, matching] unless matching.nil? 
    first, *rest = rest 
    end 
    nil 
end 

arr = [12, 7, 4, 5, 14, 9] 

find_smallest(arr, 19) #=> [5, 14] 
find_smallest(arr, 20) #=> nil 

I는 O 대 nbr - first (O (rest.size 로그)와 동일한 요소에 대한 검색 속도있어서 Array#bsearch (보다는 Enumerable#find을 사용한 (rest.size)).

Answer 2

이 하나이다 가능한 솔루션.

def sum_pairs(ints, s) 
    seen = {} 
    for i in ints do 
    return [s-i, i] if seen[s-i] 
    seen[i] = true 
    end 
    nil 
end