資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究如何使用 C# 查詢所有加起來等於零的唯一三元組？
簡單的方法是，我們可以建立三個巢狀迴圈，逐一檢查所有三個元素的和是否為零。如果三個元素的和為零，則列印這些元素。
時間複雜度 − O(n3)
空間複雜度 − O(1)
我們可以使用無序集合資料結構來儲存陣列的每個值。集合提供了在 O(1) 時間內搜尋元素的優勢。因此，對於陣列中的每一對，我們將查詢其和的負數，該負數可能存在於集合中。如果找到這樣的元素，那麼我們可以列印三元組，它將是整數對及其和的負值的組合。
時間複雜度 − O(n2)
空間複雜度 − O(n)
示例
public class Arrays{
public List<List<int>> ThreeSum(int[] nums){
List<List<int>> res = new List<List<int>>();
if (nums == null || nums.Length == 0){
return res;
}
var newnums = nums.OrderBy(x => x).ToArray();
for (int i = 0; i < newnums.Count(); i++){
int left = i + 1;
int right = newnums.Count() - 1;
while (left < right){
int sum = newnums[i] + newnums[left] + newnums[right];
if (sum == 0){
List<int> l = new List<int>();
l.Add(newnums[i]);
l.Add(newnums[left]);
l.Add(newnums[right]);
res.Add(l);
int leftValue = newnums[left];
while (left < newnums.Length && leftValue == newnums[left]){
left++;
}
int riightValue = newnums[right];
while (right > left && riightValue == newnums[right]){
right--;
}
}
else if (sum < 0){
left++;
}
else{
right--;
}
}
while (i + 1 < newnums.Length && newnums[i] == newnums[i + 1]){
i++;
}
}
return res;
}
}
static void Main(string[] args){
Arrays s = new Arrays();
int[] nums = { -1, 0, 1, 2, -1, -4 };
var ss = s.ThreeSum(nums);
foreach (var item in ss){
foreach (var item1 in item){
Console.WriteLine(item1);
}
}
}輸出
[[-1,-1,2],[-1,,0,1]]
更新於: 2021年8月17日
246 次檢視
廣告