코딩 챌린지 속도 문제

Question

두 개의 정수 배열 a 및 b와 정수 대상 값 v가 있습니다. 하나의 숫자가 a에서 가져온 것이고 b에서 다른 숫자가 추가 될 수 있는지 여부를 결정합니다 이 쌍이 있으면 true를 반환하고, 그렇지 않으면 false를 반환합니다. A = 용

예

[1, 2, 3, B = [10, 20, 30, 40, 및 v = 42, 출력.

위의 내용이 저의 문제입니다. 올바른 해결책이 있지만 솔루션을 작성하는 더 좋은 방법을 원합니다 ... 더 빨리 실행하고 싶습니다. 현재 루프 용으로 두 개를 사용하고 있습니다.

function sumOfTwo(a, b, v) { 
    for(var i=0; i < a.length; i++) { 
     for(var j=0; j < b.length; j++) { 
      if(a[i] + b[j] === v) { 
       return true; 
      } 
     } 
    } 
    return false; 
} 

어떤 도움을 주실 수 있나요? 무력 확인

Answer 1

배열 중 하나를 값으로 인덱싱 된 배열로 바꿉니다. 그런 다음 다른 배열을 반복하고 v - element이 배열의 요소인지 테스트하십시오.

function sumOfTwo(a, b, v) { 
    var test = []; 
    for (var i = 0; i < a.length; i++) { 
     test[a[i]] = true; 
    } 
    for (var i = 0; i < b.length; i++) { 
     if (test[v - b[i]]) { 
      return true; 
     } 
    } 
    return false; 
} 

Answer 2

은 O (N *의 않음)

놓아 두 배열이다. V보다 작은 요소에서 시작하고 방향을 감소로 이동합니다. (다른 사람이 확실히 오버플로) O 될 수 정렬 (nLogn)

a ---> a' O(nlogn) 
b ---> b' O(nlogn) 

binary search to elliminate a(i) > v and b(i)>v O(logn) 

은 이제 O (n 개의 * n을)로 계속 훨씬 적은 값이

Answer 3

v - a[i]의 결과를 포함 할 배열 a에서 처음으로 세트를 만들면 선형 복잡성을 달성 할 수 있습니다. 이 작업은 O(len(a))이됩니다.

그런 다음 b을 반복하고 v - a[i] 인 set.get(b)이 있는지 확인하십시오. 그럴 경우 v - a[i] === b[i]이므로 a[i] + b[i] === v입니다. 이 작업은 O(len(b))입니다.

따라서 전체 복잡도는 O(len(a)) + O(len(b))입니다 (세트에 존재하는지 확인하는 것은 O(1)입니다).

이로부터, 어레이가 동일한 길이를 갖는 경우, 복잡도는 O(2N)이고, 이는 O(N)이다.

function sumOfTwo(a, b, v) { 
 
    const setOfRemaindersFromA = new Set(a.map(num => v - num)); 
 
    return b.some(num => setOfRemaindersFromA.has(num)); 
 
} 
 

 
const a = [1, 2, 3, 4], 
 
     b = [10, 20, 30, 40]; 
 
     
 
console.log(sumOfTwo(a, b, 42)); // true 
 
console.log(sumOfTwo(a, b, 45)); // false

주 :이 방법의 사전 ES6 솔루션 Barmar's answer을 확인

여기에 코드입니다. 배열은 길이가 다른 경우

---

, 당신은 하나의 짧은에서 세트를 구축하고 모든 요소가 포함되어 있는지 확인하기 위해 하나 이상 반복해야합니다.

배열 길이를 비교하는 것은 지속적인 작업이므로 전체적인 복잡성에는 영향을 미치지 않습니다.

function sumOfTwo(a, b, v) { 
 
    const [shorter, longer] = a.length > b.length ? [b, a] : [a, b]; 
 
    const setOfRemaindersFromShorter = new Set(shorter.map(num => v - num)); 
 
    return longer.some(num => setOfRemaindersFromShorter.has(num)); 
 
} 
 

 
const a = [1, 2], 
 
     b = [10, 20, 30, 40]; 
 
     
 
console.log(sumOfTwo(a, b, 42)); // true 
 
console.log(sumOfTwo(a, b, 45)); // false

Answer 4

감사합니다!나는 다음을 시도했다 :

function sumOfTwo(a, b, v) { 
    var a = a.sort(); 
    var b = b.sort(); 
    for(var i=0; i < a.length; i++) { 
     for(var j=b.length - 1; j >= 0; j--) { 
      if(a[i] > v && b[j] < v) { 
       break; 
      } 
      if(a[i] + b[j] === v) { 
       return true; 
      } 
     } 
    } 
    return false; 
} 

더 많은 것을 향상시킬 수 있는지 알려 주시기 바랍니다!

Answer 5

는 배열을 정렬하는 경우 값이 얼마나 이상 v