ืืืขื ืืื ืืขืืขืจื ื ืื ืคืึธืจืฉืืขืืื ื ืคืื ืึทืืืขืจืืืึทืื, ืืื ืืขืคึฟืื ืขื ืืขื . ืขืก ืืื ื ืื ืืืืื ืึท ืืขืืึทื ืง ืคืื ืืื ืื ืืขืจืืืืื ืืขื ืขื ืืขืคืืจื ืืื ืืจืืืก ืืขืื ืึธืืึธืืืข ืงืึธืจืคึผืขืจืืืฉืึทื ื, ืึธืืขืจ ืืืื ืึทืืึทืื ืืืจ ืฆื ืคึฟืึทืจืฉืืืื ืืื ืื ืึทืืืขืจืืืึทื ืคึผืจืึธืืืขืืก ืืขื ืขื ืกืึทืืืื ืืื ืืคืืฉืึทื ืืื ืืื ืืขืืืขื.
ืืขืจ ืึทืจืืืงื ืืื ืึท ืืื ืคืื ืึทืงืึทืืคึผื ืืืึทื ื ืฆื ืื ืืืืืขื. ืืื ืขืก ืืื ืฆืืฉืืขืื ืืึทืืขืจืงืื ืืขื ืืืืฃ ืึทืืข ืื ืกืึทืืืฉืึทื ื ืืขืืืืื, ืคึผืืืก ืืืื ืืืืืขื ืข ืืืขืจืกืืข ืคืื โโโโืื ืืืืืื ื ืืื ืืืฉืึทืืืึทืกืงืจืืคึผื. ืื ื ืืึทื ืกืื ืคืื ืืขืืขืจ ืึทืืืขืจืืืึทื ืืขื ืขื ืืืื ืืืกืงืึทืกื.
ืืืจ ืืขืจืืึธื ืขื ืืืจ: ืคึฟืึทืจ ืึทืืข ืืืืขื ืขืจ ืคืื "ืืืจ" - ืึท ืึทืจืึธืคึผืจืขืืขื ืขื ืคืื 10 ืจืืื ืืืขื ืืืจ ืคืึทืจืฉืจืืึทืื ืืื ืงืืื ืกืงืืืืึธืงืก ืงืืจืก ื ืืฆื ืื ืคึผืขืจืืึธืืฉืึทื ืึทื ืงืึธื "ืืืจ".
Skillbox ืจืขืงืึทืืขื ืื: ืคึผืจืึทืงืืืฉ ืงืืจืก .
ืืืกืืึธืืื ื ืคืื ืื ืคึผืจืึธืืืขื
ืืืจ ืืึทืงืืืขื ืึท ืึธืจืืขืจื ืืขื ืืข ืืื ืึท ืกืคึผืขืฆืืคืืฉ ืืืขืจื. ืขืก ืืื ืืขืจืืืขืจ ืืขืืขืื ืฆื ืฉืึทืคึฟื ืึท ืคึฟืื ืงืฆืืข ืืืึธืก ืงืขืจื ืืืช ืึธืืขืจ ืคืึทืืฉ ืืืคึผืขื ืืื ื ืืืืฃ ืฆื ืื ืกืึทืืึทืงื ืคืื ืงืืื ืฆืืืื ื ืืืขืจื ืืื ืื ืืขื ืืข ืงืขื ืขื ืืืืึทื ืึท ืืขืืขืื ืืืขืจื.
ืืื ืื ืืขืจืข ืืืขืจืืขืจ, ืืขื ืขื ืขืก ืฆืืืื ืื ืืึทืืืฉืขืจื ืืื ืื ืืขื ืืข, x ืืื y, ืึทื ืืืขื ืืืกืืฃ ืฆืืืึทืืขื ืืืืึทื ืื ืกืคึผืขืกืืคืืขื ืืืขืจื?
ืืืึทืฉืคึผืื ื
ืืืื ืืืจ ืืขื ืขื ืืขืืขืื ืึท ืืขื ืืข [1, 2, 4, 9] ืืื ืื ืืืขืจื ืืื 8, ืื ืคึฟืื ืงืฆืืข ืืืขื ืฆืืจืืงืงืืืขื ืคืึทืืฉ ืืืืึทื ืงืืื ืฆืืืื ื ืืืขืจื ืืื ืื ืืขื ืืข ืงืขื ืขื ืืืืื ืึทืจืืืฃ ืฆื 8.
ืืืึทืฉืคึผืื ื
ืืืขืจ ืืืื ืขืก ืืื ืึท ืืขื ืืข [1, 2, 4, 4] ืืื ืื ืืืขืจื ืืื 8, ืื ืคึฟืื ืงืฆืืข ืืึธื ืฆืืจืืงืงืืืขื ืืืช ืืืืึทื 4 + 4 = 8.
ืืืืืื ื 1: ืืจืึธื ืงืจืึทืคื
ืฆืืื ืงืึทืืคึผืืขืงืกืืื: ืึธ(ื ยฒ).
ืคึผืืึทืฅ ืงืึทืืคึผืืขืงืกืืื: ืึธ (ืงืกื ืืืงืก).
ืื ืืขืจืกื ืงืืึธืจ ืืื ืืขืจ ืืึธื ืืืึทืืฉ ืืื ืฆื ื ืืฆื ืึท ืคึผืึธืจ ืคืื ื ืขืกืืขื ืืืคึผืก.
const findSum = (arr, val) => {
for (let i = 0; i < arr.length; i++) {
for (let j = 0; j < arr.length; j++) {
if (i !== j && arr[i] + arr[j] === val) {
return true;
};
};
};
return false;
};ืื ืืืืืื ื ืืื ื ืืฉื ืขืคืขืงืืืื ืืืืึทื ืขืก ืืฉืขืงืก ืืขืืขืจ ืืขืืืขื ืกืึทืืึทืงื ืคืื ืฆืืืื ืขืืขืืขื ืื ืืื ืื ืืขื ืืข ืืื ืืืื ืงืึทืืคึผืขืจื ืืขืืขืจ ืคึผืึธืจ ืคืื ืื ืืืกืขืก ืฆืืืื ืืึธื. (ืืืฉื, ืืืขื ืืื = 1 ืืื ืืืฉ = 2 ืืื ืคืืงืืืฉ ืื ืืขืืืข ืืื ืงืึทืืคึผืขืจืื ื ืืื i = 2 ืืื ืืืฉ = 1, ืึธืืขืจ ืืื ืืขื ืืืืืื ื ืืืจ ืคึผืจืืืืจื ืืืืืข ืึธืคึผืฆืืขืก).
ืืืืึทื ืืื ืืืขืจ ืืืืืื ื ื ืืฆื ืึท ืคึผืึธืจ ืคืื ื ืขืกืืขื ืคึฟืึทืจ ืืืคึผืก, ืขืก ืืื ืงืืืึทืืจืึทืืืง ืืื O (Nยฒ) ืฆืืื ืงืึทืืคึผืืขืงืกืืื.
ืืืืืื ื 2: ืืืื ืขืจื ืืืื
ืฆืืื ืงืึทืืคึผืืขืงืกืืื: O(Nlog(N)).
ืคึผืืึทืฅ ืงืึทืืคึผืืขืงืกืืื: ืึธ (1).
ืืื ื ืื ืขืจืืื ืืขื ืขื ืึธืจืืขืจื, ืืืจ ืงืขื ืขื ืืืื ืคึฟืึทืจ ืึท ืืืืืื ื ื ืืฆื ืืืื ืขืจื ืืืื. ืืึธืก ืืื ืื ืืขืจืกื ืขืคืขืงืืืื ืึทืืืขืจืืืึทื ืคึฟืึทืจ ืึธืจืืขืจื ืขืจืืื. ืืืื ืขืจื ืืืื ืืื ืืื ืึท ืคืืืกื ืืืง ืฆืืื ืคืื ืึธ (ืืึธื (ืขื)). ืึธืืขืจ, ืืืจ ื ืึธื ืืึทืจืคึฟื ืฆื ื ืืฆื ืึท ืคึฟืึทืจ ืฉืืืืฃ ืฆื ืงืึธื ืืจืึธืืืจื ืืขืืขืจ ืขืืขืืขื ื ืงืขืื ืึทืืข ืื ืืขืจืข ืืืึทืืืขืก.
ืืึธ ืก ืืืึธืก ืึท ืืืืืื ื ืืื ืงืืงื ืืื. ืฆื ืืึทืื ืื ืืื ืื ืงืืึธืจ, ืืืจ ื ืืฆื ืึท ืืึทืืื ืืขืจ ืคืื ืงืฆืืข ืฆื ืงืึธื ืืจืึธืืืจื ืืืื ืขืจื ืืืื. ืืื ืืืื ืื removeIndex () ืคึฟืื ืงืฆืืข, ืืืึธืก ืงืขืจื ืื ืืืขืจืกืืข ืคืื โโืื ืืขื ืืข ืืื ืืก ืื ืืขืืขืื ืืื ืืขืงืก.
const findSum = (arr, val) => {
for (let i = 0; i < arr.length; i++){
if (binarySearch(removeIndex(arr, i), val - arr[i])) {
return true;
}
};
return false;
};
const removeIndex = (arr, i) => {
return arr.slice(0, i).concat(arr.slice(i + 1, arr.length));
};
const binarySearch = (arr, val) => {
let start = 0;
let end = arr.length - 1;
let pivot = Math.floor(arr.length / 2);
while (start < end) {
if (val < arr[pivot]) {
end = pivot - 1;
} else if (val > arr[pivot]) {
start = pivot + 1;
};
pivot = Math.floor((start + end) / 2);
if (arr[pivot] === val) {
return true;
}
};
return false;
};ืืขืจ ืึทืืืขืจืืืึทื ืกืืึทืจืฅ ืคืื ืืื ืืขืงืก [0]. ืืขืจื ืึธื, ืขืก ืงืจืืืืฅ ืึท ืืืขืจืกืืข ืคืื โโโโืื ืืขื ืืข ืขืงืกืงืืืืื ื ืืขืจ ืขืจืฉืืขืจ ืืื ืืขืงืก ืืื ื ืืฆื ืืืื ืขืจื ืืืื ืฆื ืืขื ืืืื ืืืื ืขืจ ืคืื ืื ืจืืขื ืืืึทืืืขืก ืงืขื ืขื ืืืื ืืืกืืฃ ืฆื ืื ืืขื ืืข ืฆื ืคึผืจืึธืืืฆืืจื ืื ืืขืืขืื ืกืึทืืึทืงื. ืืขื ืงืึทืืฃ ืืื ืืขืืื ืึทืืึธื ืคึฟืึทืจ ืืขืืขืจ ืขืืขืืขื ื ืืื ืื ืืขื ืืข.
ืื ืคึฟืึทืจ ืฉืืืืฃ ืืื ืืืขื ืืึธืื ืึท ืืื ืขืึทืจ ืฆืืื ืงืึทืืคึผืืขืงืกืืื ืคืื O(N), ืึธืืขืจ ืื ืืขืจ ืคึฟืึทืจ ืฉืืืืฃ ืืืจ ืืืจืืคืืจื ืึท ืืืื ืขืจื ืืืื, ืืืึธืก ืืื ืึท ืงืืืืขืืืืง ืฆืืื ืงืึทืืคึผืืขืงืกืืื ืคืื O(Nlog(N)). ืื ืืืืืื ื ืืื ืืขืกืขืจ ืืื ืื ืคืจืืขืจืืืงืข, ืึธืืขืจ ืขืก ืืื ื ืึธื ืคึผืืึทืฅ ืคึฟืึทืจ ืคึฟืึทืจืืขืกืขืจืื ื.
ืืืืืื ื 3: ืืื ืขืึทืจ ืฆืืื
ืฆืืื ืงืึทืืคึผืืขืงืกืืื: ืึธ(ืขื).
ืคึผืืึทืฅ ืงืึทืืคึผืืขืงืกืืื: ืึธ (ืงืกื ืืืงืก).
ืืืฆื ืืืจ ืืืขืื ืกืึธืืืืข ืื ืคึผืจืึธืืืขื, ืืขืืขื ืงืขื ืึทื ืื ืืขื ืืข ืืื ืืืืกืืขืฉืืขืื. ืื ืืืืืื ื ืืื ืฆื ื ืขืืขื ืฆืืืื ื ืืืขืจื: ืืืื ืขืจ ืืื ืื ืึธื ืืืื ืืื ืืืื ืขืจ ืืื ืื ืกืืฃ. ืืืื ืืขืจ ืจืขืืืืืึทื ืืื ืึทื ืืขืจืฉ ืคืื ืื ืคืืจืืื ืื, ืืืืฉื ืื ืกืืึทืจืืื ื ืืื ืกืึธืฃ ืคืื ืงืื.
ืืืืขื ืืฉืึทืืืึทืื ืืืจ ืืืขืื ืึธืืขืจ ืืจืขืคื ืื ืืขืืขืื ืืืขืจื ืืื ืฆืืจืืงืงืืืขื ืืืช, ืึธืืขืจ ืื ืึธื ืืืื ืืื ืกืืฃ ืคืื ืงืื ืืืขืื ืงืึทื ืืืขืจืืืฉ ืืื ืฆืืจืืงืงืืืขื ืคืึทืืฉ.
const findSum = (arr, val) => {
let start = 0;
let end = arr.length - 1;
while (start < end) {
let sum = arr[start] + arr[end];
if (sum > val) {
end -= 1;
} else if (sum < val) {
start += 1;
} else {
return true;
};
};
return false;
};
ืืืฆื ืึทืืฅ ืืื ืืื, ืื ืืืืืื ื ืืืื ื ืฆื ืืืื ืึธืคึผืืืืึทื. ืืืขืจ ืืืขืจ ืงืขื ืขื ืืึทืจืึทื ืืืจื ืึทื ืื ืืขื ืืข ืืื ืึธืจืืขืจื?
ืืืืก ืืขื?
ืืื ืขืจืฉืืขืจ ืืืืง, ืืืจ ืงืขื ืืึธืื ืคืฉืื ืึธืจืืขืจื ืื ืืขื ืืข ืขืจืฉืืขืจ ืืื ืืขืจื ืึธื ืืขืืืืื ื ืื ืืืืืื ื ืืืืื. ืึธืืขืจ ืืื ืืืขื ืืึธืก ืืืืจืงื ืื ืืืจืืคืืจืื ื ืฆืืื?
ืืขืจ ืืขืกืืขืจ ืึทืืืขืจืืืึทื ืืื ืงืืืืงืกืึธืจื ืืื ืฆืืื ืงืึทืืคึผืืขืงืกืืื ืึธ (Nlog (N)). ืืืื ืืืจ ื ืืฆื ืขืก ืืื ืืื ืืืขืจ ืึธืคึผืืืืึทื ืืืืืื ื, ืขืก ืืืขื ืืืืฉื ืืืึทื ืคืึธืจืฉืืขืืื ื ืคืื O(N) ืฆื O(Nlog(N)). ืืื ืขืก ืืขืืืขื ืฆื ืืขืคึฟืื ืขื ืึท ืืื ืขืึทืจ ืืืืืื ื ืืื ืึท ืึทื ืึธืจืืขืจื ืืขื ืืข?
ืืืืืื ื 4
ืฆืืื ืงืึทืืคึผืืขืงืกืืื: ืึธ(ืขื).
ืคึผืืึทืฅ ืงืึทืืคึผืืขืงืกืืื: ืึธ (ืขื).
ืืึธ, ืขืก ืืื ืึท ืืื ืขืึทืจ ืืืืืื ื; ืฆื ืืึธื ืืึธืก, ืืืจ ืืึทืจืคึฟื ืฆื ืฉืึทืคึฟื ืึท ื ืืึทืข ืืขื ืืข ืืื ืื ืจืฉืืื ืคืื ืฉืืืขืืขืืขื ืืืึธืก ืืืจ ืืขื ืขื ืงืืงื ืคึฟืึทืจ. ืื ืืึทื ืื-ืึทืืืขืง ืืึธ ืืื ืืขืจ ืืึผืจืื ืืึทื ืืฅ: ืืึธืก ืืื ืืขืจ ืืืืื ืืืืืื ื ืืื ืื ืคึผืึทืคึผืืจ ืืื ืคึผืืึทืฅ ืงืึทืืคึผืืขืงืกืืื ืืจืขืกืขืจ ืืื ืึธ (1).
ืืืื ืืขืจ ืขืจืฉืืขืจ ืืืขืจื ืคืื ืึท ืืขืืขืื ืืขื ืืข ืืื 1 ืืื ืื ืืืื ืืืขืจื ืืื 8, ืืืจ ืงืขื ืขื ืืืืื ืื ืืืขืจื 7 ืฆื ืื "ืืืื ืืืึทืืืขืก" ืืขื ืืข.
ืืขืจื ืึธื, ืืืขื ืืืจ ืคึผืจืึธืฆืขืก ืืขืืขืจ ืขืืขืืขื ื ืคืื ืื ืืขื ืืข, ืืืจ ืงืขื ืขื ืงืึธื ืืจืึธืืืจื ืื ืืขื ืืข ืคืื โโโโ"ืืืื ืืืึทืืืขืก" ืืื ืืขื ืืืื ืืืื ืขืจ ืคืื ืืื ืืื ืืืืึทื ืฆื ืืื ืืืขืจ ืืืขืจื. ืืืื ืืึธ, ืฆืืจืืงืงืืืขื ืืืช.
const findSum = (arr, val) => {
let searchValues = [val - arr[0]];
for (let i = 1; i < arr.length; i++) {
let searchVal = val - arr[i];
if (searchValues.includes(arr[i])) {
return true;
} else {
searchValues.push(searchVal);
}
};
return false;
};ืื ืืงืขืจ ืคืื ืื ืืืืืื ื ืืื ืึท ืคึฟืึทืจ ืฉืืืืฃ, ืืืึธืก, ืืื ืืืจ ืืขืืขื ืืืืื, ืืื ืึท ืืื ืขืึทืจ ืฆืืื ืงืึทืืคึผืืขืงืกืืื ืคืื O(N).
ืื ืจืืข ืืืขืจืึทืืืื ืืืื ืคืื ืืื ืืืขืจ ืคึฟืื ืงืฆืืข ืืื Array.prototype.include (), ืึท ืืืฉืึทืืืึทืกืงืจืืคึผื ืืืคึฟื ืืืึธืก ืืืขื ืฆืืจืืงืงืืืขื ืืืช ืึธืืขืจ ืคืึทืืฉ ืืืคึผืขื ืืื ื ืืืืฃ ืฆื ืื ืืขื ืืข ืึผืืื ืื ืืขืืขืื ืืืขืจื.
ืฆื ืจืขืืขื ืขื ืื ืฆืืื ืงืึทืืคึผืืขืงืกืืื ืคืื Array.prototype.includes(), ืืืจ ืงืขื ืขื ืงืืงื ืืื ืื ืคึผืึธืืืคืืื ืฆืืืขืฉืืขืื ืืืจื MDN (ืืื ืืขืฉืจืืื ืืื ืืืฉืึทืืืึทืกืงืจืืคึผื) ืึธืืขืจ ื ืืฆื ืึท ืืขืืึธื ืืื ืื ืืงืืจ ืงืึธื ืคืื ืึท ืืืฉืึทืืืึทืกืงืจืืคึผื ืืึธืืึธืจ ืึทืืึท ืืื Google V8 (C ++).
// https://tc39.github.io/ecma262/#sec-array.prototype.includes
if (!Array.prototype.includes) {
Object.defineProperty(Array.prototype, 'includes', {
value: function(valueToFind, fromIndex) {
if (this == null) {
throw new TypeError('"this" is null or not defined');
}
// 1. Let O be ? ToObject(this value).
var o = Object(this);
// 2. Let len be ? ToLength(? Get(O, "length")).
var len = o.length >>> 0;
// 3. If len is 0, return false.
if (len === 0) {
return false;
}
// 4. Let n be ? ToInteger(fromIndex).
// (If fromIndex is undefined, this step produces the value 0.)
var n = fromIndex | 0;
// 5. If n โฅ 0, then
// a. Let k be n.
// 6. Else n < 0,
// a. Let k be len + n.
// b. If k < 0, let k be 0.
var k = Math.max(n >= 0 ? n : len - Math.abs(n), 0);
function sameValueZero(x, y) {
return x === y || (typeof x === 'number' && typeof y === 'number' && isNaN(x) && isNaN(y));
}
// 7. Repeat, while k < len
while (k < len) {
// a. Let elementK be the result of ? Get(O, ! ToString(k)).
// b. If SameValueZero(valueToFind, elementK) is true, return true.
if (sameValueZero(o[k], valueToFind)) {
return true;
}
// c. Increase k by 1.
k++;
}
// 8. Return false
return false;
}
});
}ืืึธ ืื ืืืขืจืึทืืืื ืืืื ืคืื Array.prototype.include() ืืื ืื ืืฉืขืช ืฉืืืืฃ ืืื ืฉืจืื 7 ืืืึธืก (ืึผืืขื) ืืจืึทืืืขืจืกื ืื ืืื ืฆืข ืืขื ื ืคืื ืื ืืขืืขืื ืืขื ืืข. ืืขื ืืืื ืึทื ืืืึทื ืฆืืื ืงืึทืืคึผืืขืงืกืืื ืืื ืืืื ืืื ืขืึทืจ. ื ื, ืืื ื ืขืก ืืื ืฉืืขื ืืืง ืืืื ืฉืจืื ืืื ืืขืจ ืืื ืืืขืจ ืืืืคึผื ืืขื ืืข, ืื ืฆืืื ืงืึทืืคึผืืขืงืกืืื ืืื ืึธ (N + (N - 1)). ื ืืฆื ืืื ืึธ ื ืึธืืึทืืืึธื, ืืืจ ืคืึทืจืคึผืึธืฉืขืืขืจื ืขืก ืฆื O (N) - ืืืืึทื ืขืก ืืื N ืืืึธืก ืืื ืื ืืจืขืกืืข ืคึผืจืึทื ืืืขื ืื ืงืจืืกืื ื ืื ืึทืจืืึทื ืฉืจืืึทื ืืจืืืก.
ืืืขืื ืกืคึผืืืฉืึทื ืงืึทืืคึผืืขืงืกืืื, ืึทื ื ืึธื ืืขื ืืข ืืื ืืืจืฃ ืืืขืืขื ืก ืืขื ื ืืืจืขืจื ืื ืึธืจืืืื ืขื ืืขื ืืข (ืืื ืืก ืืืื ืขืจ, ืืึธ, ืึธืืขืจ ืืึธืก ืงืขื ืขื ืืืื ืืืื ืึธืจืืจื), ืจืืืึทืืืื ื ืืื O (N) ืกืคึผืืืฉืึทื ืงืึทืืคึผืืขืงืกืืื. ื ื, ืืขืืืืงืกื ืืึผืจืื ืืึทื ืืฅ ืื ืฉืืจื ืืึทืงืกืืืื ืขืคืขืงืืืืืงืืึทื ืคืื ืื ืึทืืืขืจืืืึทื.
ืืื ืืึธืคึฟื ืืืจ ืืขืคึฟืื ืขื ืืขื ืึทืจืืืงื ื ืืฆืืง ืืื ืึท ืืขืกืึธืคืข ืฆื ืืืื ืืืืืขื ืืื ืืขืจืืืื. ืขืก ืืืืืื ืึทื ืึท ืคึผืฉืื ืคึผืจืึธืืืขื ืงืขื ืขื ืืืื ืกืึทืืืื ืืื ืขืืืขืืข ืคืึทืจืฉืืืขื ืข ืืืขืื ืืื ืคืึทืจืฉืืืขื ืข ืึทืืึทืื ืฅ ืคืื ืจืขืกืืจืกื ืืขื ืืฆื (ืฆืืื, ืืึผืจืื).
Skillbox ืจืขืงืึทืืขื ืื:
- ืึทืคึผืคึผืืืขื ืึธื ืืืื ืงืืจืก .
- ืึธื ืืืื ืงืืจืก .
- ืคึผืจืึทืงืืืฉ ืืึธืจ ืงืืจืก .
ืืงืืจ: www.habr.com