我正在嘗試撰寫一個函式，該函式采用非負整數，并回傳一個非負整數對串列，其值 - 當平方時 - 總和為給定整數。
例子：
5 --> [ [1, 2] ]
25 --> [ [0, 5], [3, 4] ]
325 --> [ [1, 18], [6, 17], [10, 15] ]
我的解決方案在 IDE 中作業，但是當我將其提交給 codewars 時，我收到退出代碼錯誤 139：致命錯誤：無效的表大小分配失敗 - JavaScript 堆記憶體不足。codewars 檔案表明這是由于演算法效率低下造成的。
最初我的解決方案包含一個嵌套回圈，這會導致運行時間過長，但我已經重構了我的代碼以洗掉它。盡管降低了復雜性，但我仍然遇到同樣的錯誤。
有什么建議可以進一步降低復雜性嗎？
const allSquaredPairs = (n) => {
//get array of all numbers between 0 and sqrt of n
let possibleNums = Array(n)
.fill()
.map((_, i) => {
if ((i 1) ** 2 <= n) return i 1; //only numbers lesser than sqrt of n
})
.filter(n => n!=undefined)
possibleNums = [0, ...possibleNums];
const matchingPairs = [];
while (possibleNums.length){
const num1 = possibleNums[0];
const num2 = possibleNums[possibleNums.length-1];
const sum = num1 ** 2 num2 ** 2
if (sum === n) matchingPairs.push([num1, num2]);
if (sum > n ) possibleNums.pop()
else possibleNums.shift()
}
return matchingPairs;
};
console.log(allSquaredPairs(25));
uj5u.com熱心網友回復：
您的解決方案分配了一個長度為 n 的陣列，然后對其進行迭代。這意味著您的解決方案的記憶體需求會隨著 n 的增加而線性增加。
您可以在不分配該陣列的情況下實作這一點，這樣無論 n 的值有多大，記憶體需求都是恒定的。
const examples = [
{ input: 5, output: [ [1, 2] ] },
{ input: 25, output: [ [0, 5], [3, 4] ] },
{ input: 325, output: [ [1, 18], [6, 17], [10, 15] ] },
{ input: Number.MAX_SAFE_INTEGER, output: [] }
];
function allSquaredPairs(n) {
const matchingPairs = [];
const smallestIntegerLargerThanSquareRootOfN = Math.ceil(Math.sqrt(n));
let lowerBound = 0;
let upperBound = smallestIntegerLargerThanSquareRootOfN;
while (lowerBound < upperBound) {
const sum = lowerBound ** 2 upperBound ** 2;
if (sum === n) {
matchingPairs.push([lowerBound, upperBound]);
lowerBound = 1;
} else if (sum < n) lowerBound = 1;
else if (sum > n) upperBound -= 1;
else console.log("ERROR!")
}
return matchingPairs;
}
examples.forEach(({ input, output}) => console.log({ n: input, expected: JSON.stringify(output), " actual": JSON.stringify(allSquaredPairs(input)) }));作為一個興趣點，我let whatever = new Array(n)在函式的開頭嘗試了這個，并且對于它拋出的最大安全整數測驗用例RangeError: invalid array length。這與您看到的錯誤不同，但它確實說明了分配長度陣列n會使事情復雜化。
轉載請註明出處，本文鏈接：https://www.uj5u.com/yidong/404747.html
標籤：