首頁猿問在數組中找到三元組 (a, b...

在數組中找到三元組 (a, b ,c)，使得 a + b + c = 0

Java

慕的地6264312 2022-11-02 10:46:09

我想在一個數組中找到所有不同的三元組（a，b，c），使得 a + b + c = 0。我在 java 中實現了該算法，但是當輸入很大時（例如 100,000 個零等），我得到了 TLE。對于 100,000 個零，它應該只輸出 (0, 0, 0)。有人可以就如何加快速度提供一些想法嗎？下面是我寫的函數。它將一個數組作為輸入并返回所有具有所需屬性的唯一三元組作為列表。public List<List<Integer>> threeSum(int[] nums) { Arrays.sort(nums); List<List<Integer>> ll = new ArrayList<List<Integer>>(); for(int i = 0; i < nums.length - 1; i++){ int x = nums[i]; int start = i + 1; int end = nums.length - 1; int sum = -x; while(start < end){ int y = nums[start] + nums[end]; if(y == sum){ List<Integer> list = new ArrayList<Integer>(); list.add(nums[start]); list.add(nums[end]); list.add(x); Collections.sort(list); ll.add(list); } if(y < sum) start++; else end--; } } return ll.stream() .distinct() .collect(Collectors.toList()); }

查看完整描述

4 回答

料青山看我應如是

TA貢獻1772條經驗獲得超8個贊

我認為你對時間復雜度無能為力。兩個索引必須獨立探索數組（起點/終點除外），而第三個索引可以受到約束，就像在您的算法中一樣，這意味著復雜度為 O(n 2 )。這支配了數組的初步排序，即 O(n·log(n))，以及一個“去乘”步驟，即 O(n)。

我寫了“demultiplication”，因為“deduplication”是不可取的：假設數組是[-1,-1,0,2]. 對其進行重復數據刪除將消除唯一的解決方案。但是一個解不能包含超過兩次的整數，除非它是0，在這種情況下[0,0,0]是一個解。所有出現兩次以上的整數，或者在的情況下出現三次0，都是冗余的，可以在排序之后和主算法之前一次性消除。

至于因素，可以通過將探索限制在有意義的范圍內來改進。我會修改您的算法，使您移動直到它們相遇的一對索引從它們相遇的地方開始向外，直到較低的索引到達主要索引，或者較高的索引到達數組的末尾。掃描的起點可以在掃描中被記住，隨著主索引向上移動，向下調整它。如果起始點（實際上是一對相鄰索引的起始對）在當前范圍之外，則可以省略掃描。找到初始起點是算法的附加部分，排序后可能是 O(log(n))，但非常簡單的 O(n) 版本也可以。

抱歉，我現在沒有時間將以上所有內容翻譯成 Java 代碼。我現在能做的就是記下數組排序后的“去乘”代碼（未經測試）：

int len = 1;

int last = nums[0];

int count = 1;

for (int i = 1; i < nums.length; i++) {

int x = nums[i];

if (x != last) {

nums[len++] = x;

last = x;

count = 1;

} else if (count < 2 || x == 0 && count < 3) {

nums[len++] = x;

count++;

}

// use len instead of nums.length from this point on

反對回復 2022-11-02

MMTTMM

TA貢獻1869條經驗獲得超4個贊

我看到的最重要的部分是，對于 100,000 個零的示例，您將針對每個可能的情況點擊 if (y == sum) 塊。這似乎是性能最差的情況，因為您永遠不會跳過該塊。

我能看到的最大改進是首先對您的輸入進行重復數據刪除。不幸的是，集合不起作用，因為我們仍然需要維護最多三個相同的條目。因此，我的建議是，在您排序之后，循環遍歷輸入數組，并且每當您連續遇到三個以上的數字副本時，刪除額外的。他們不需要解決問題，只是浪費時間。

反對回復 2022-11-02

哈士奇WWW

TA貢獻1799條經驗獲得超6個贊

您可以創建一個List（其實現是ArrayList）來存儲您已經擁有的組合。始終以以下格式存儲新值

a,b,c

其中a <= b <= c

因此，每當您獲得可能已經找到或尚未找到的組合時，請生成String相同格式的 a 并檢查它是否存在于您的List. 如果是這樣，那就不要add了。否則add它給你的List. 在此之后，您可以將找到的值轉換為數值。如果你想加快速度，你可以創建一個class類似的：

class XYZ {

public int x;

public int y;

public int z;

public XYZ(int x, int y, int z) {

this.x = x;

this.y = y;

this.z = z;

}

public isMatch(int x, int y, int z) {

return (this.x == x) &&

(this.y == y) &&

(this.z == z);

}

public static boolean anyMatch(List<XYZ> list, int x, int y, int z) {

for (XYZ xyz : list) {

if (xyz.isMatch(x, y, z)) return true;

}

return false;

}

public static void addIfNotExists(List<XYZ> list, int x, int y, int z) {

if (!anyMatch(list, x, y, z)) list.add(new XYZ(x, y, z));

}

并且您可以將此類用于您的目的，只需確保x <= y <= z。

反對回復 2022-11-02

慕沐林林

TA貢獻2016條經驗獲得超9個贊

最后過濾非唯一三元組可以通過使用按排序順序存儲三元組的哈希表來消除，因此三元組的所有組合（具有不同排序）僅存儲一次。

使用 hashmap/hashset 而不是 arraylist。

HashSet<List<Integer>> ll = new HashSet<List<Integer>>();

. . .

list.addAll(a,b,c)

Collections.sort(list)

ll.add(list)

除此之外，您還可以使用另一個查找表來確保 nums[] 中的每個重復項僅用于計算三元組一次。

lookup_table = HashMap();

for(int i = 0; i < nums.length - 1; i++){

// we have already found triplets starting from nums[i]

// eg. [-1,-1,0,1], we don't need to calculate

// the same triplets for the second '-1'.

if (lookup_table.contains(nums[i]))

continue;

// Mark nums[i] as 'solved'

lookup_table.add(nums[i])

// usual processing here

int x = nums[i];

或者，由于您的 nums[] 列表已經排序，您可以跳過重復項，無需另一個查找表。

i = 0;

while (i < nums.length - 1){

// we have already found triplets starting from nums[i]

// eg. [-1,-1,0,1], we don't need to calculate

// the same triplets for the second '-1'.

x = nums[i];

// skip repeating items

while (x == nums[i++]);

// usual processing here

. . .

i++;

}

然后您可以在最后將哈希集作為列表返回。

反對回復 2022-11-02

4 回答
0 關注
385 瀏覽

關注

添加回答

舉報

0/150

提交

取消

亚洲在线久爱草,狠狠天天香蕉网,天天搞日日干久草,伊人亚洲日本欧美

熱搜

最近搜索清空

在數組中找到三元組 (a, b ,c)，使得 a + b + c = 0

在數組中找到三元組 (a, b ,c)，使得 a + b + c = 0

4 回答

添加回答

在數組中找到三元組 (a, b ,c)，使得 a + b + c = 0

在數組中找到三元組 (a, b ,c)，使得 a + b + c = 0