我正在嘗試撰寫一個將采用陣列和目標整數的函式。結果，我想回傳所有可能的對，它們的總和小于目標整數。結果應避免重復。例如：[2,4] 和 [4,2] 是一樣的。
示例：輸入：[1,2,2,3,4,5]，6 輸出：[[1,2],[1,3],[1,4],[2,2]]
下面是我能想到的，但問題是它會有重復，而且它是嵌套回圈，在時間復雜度方面對于大 O 有 n 平方。有更好的解決方案嗎？我怎樣才能擺脫重復？
function twoNumSum(array, targetNum) {
let result = [];
for (i = 0; i < array.length; i ) {
for (j = i 1; j < array.length; j ) {
if (array[i] array[j] < targetNum) {
if (!result[(array[i], array[j])]) {
result.push([array[i], array[j]]);
}
}
}
}
return result;
}
//Test for my solution
console.log(twoNumSum([1, 2, 3, 4], 4));//output=[1,2]
console.log(twoNumSum([1, 2, 3], 3)),6//output=[]
console.log(twoNumSum([1, 2, 2, 3, 4], 5));//output=[[1,2],[1,2],[1,3],[2,2] DUPLICATES of [1,2]
uj5u.com熱心網友回復：
考慮陣列中每個可能對的總和小于目標的情況（例如[1,2,3,4], target=10）。有n^2有效的對，因此您的時間復雜度不太可能比O(n^2).
為了處理重復項，您可以對這些對進行排序并將這些對[smaller element, bigger element]存盤在一個集合中。
uj5u.com熱心網友回復：
您可以使用Set,JSON.stringify和JSON.parse
Set確保您沒有重復項，但為了在陣列上執行此操作，我將其轉換為 json 字串。
當您擁有唯一值時，您可以將 Set 轉換為陣列并將 json 字串決議回陣列
function twoNumSum(array, targetNum) {
let result = new Set();
for (i = 0; i < array.length; i ) {
for (j = i 1; j < array.length; j ) {
if (array[i] array[j] < targetNum) {
result.add(JSON.stringify([array[i], array[j]]));
}
}
}
return [...result].map(JSON.parse);
}
//Test for my solution
console.log(twoNumSum([1, 2, 2, 3, 4], 6))uj5u.com熱心網友回復：
為避免重復，我使用Object而不是Array存盤對
在添加對之前，首先檢查對是否不在物件鍵中
!(pairs.toString() in result)
我使用了兩個回圈，第二個從當前索引的下一個開始i（以避免將第一對與自身進行比較）
for (let j = i 1; j < array.length - i - 1; j )
function twoNumSum(array, targetNum) {
let result = {};
for (i = 0; i < array.length; i ) {
const currNumber = array[i];
for (let j = i 1; j < array.length - i - 1; j ) {
const nextNumber = array[j];
const pairs = [currNumber, nextNumber];
const innserSum = pairs[0] pairs[1];
if (innserSum < targetNum && !(pairs.toString() in result)) {
result[pairs] = pairs;
}
}
}
return Object.values(result);
}
console.log(JSON.stringify(twoNumSum([1, 2, 2, 3, 4], 6))); //[[1,2],[1,3],[2,2]]uj5u.com熱心網友回復：
只需對串列進行排序并首先洗掉重復項。
看到這個看看[1,2,2,3]。洗掉重復的產量[1,2,3]- 重復的條目會產生重復的結果。因此，首先擺脫它們。
如果您不喜歡修改輸入陣列，只需復制它并進行處理。
您還可以洗掉所有值大于目標整數的條目。它們不會成為任何解決方案的一部分（我假設只有非負值，否則只需跳過該部分）。
復制陣列在O(n).
排序在O(n log(n)).
洗掉重復項在O(n).
洗掉大于目標整數的值O(n)（陣列已排序，因此從陣列的末尾開始，所以實際上它在O(m)哪里m是大于目標整數的元素數，具體取決于您可能聲稱的資料m < n）。
您可以通過這種方式減少輸入，使其更輕松、更快捷。另一方面，你不能低于O(n^2)我所能看到的。您必須遍歷元素并構建對。
如果您事先洗掉大于目標整數的值，那么您可以說它在O((n-m)^2).
關注演算法的效率是很有趣的。但有時我們想知道或想提高復雜性走得太遠了。具有諷刺意味的是，這樣做我們往往會增加解決問題的復雜性。
我將從最簡單可行的方法開始。如果它有效，那就太好了。如果需要改進，那么我們可以從那里開始。
轉載請註明出處，本文鏈接：https://www.uj5u.com/yidong/489536.html
標籤：javascript 算法