資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學如何使用C#查詢接近給定目標值的唯一三元組？
雙指標模式，類似於三數之和為零。我們可以採用類似的方法迭代陣列，每次取一個數字。在每一步，我們將儲存三元組與目標數字之間的差值，並在每一步將其與到目前為止的最小目標差值進行比較，以便最終可以返回具有最接近和的三元組。
時間複雜度
對陣列進行排序需要O(N*logN)。總的來說，threeSumClosest()需要O(N * logN + N^2)，這在漸近意義上等價於O(N^2)。
空間複雜度
上述演算法的空間複雜度為O(N)，這是排序所需的。
示例
public class Arrays{
public int ThreeSumClosest(int[] num, int target){
if (num == null || num.Length == 0){
return -1;
}
int[] nums = num.OrderBy(x => x).ToArray();
int initialclosest = nums[0] + nums[1] + nums[2];
for (int i = 0; i < nums.Count(); i++){
int left = i + 1;
int right = nums.Length - 1;
while (left < right){
int newClosest = nums[i] + nums[left] + nums[right];
if (Math.Abs(newClosest - target) < Math.Abs(initialclosest - target)){
initialclosest = newClosest;
}
if (newClosest == target){
return newClosest;
}
else if (newClosest < target){
left++;
}
else
{
right--;
}
}
}
return initialclosest;
}
}
static void Main(string[] args){
Arrays s = new Arrays();
int[] nums = { -1, 2, 1, -4 };
Console.WriteLine(s.ThreeSumClosest(nums, 1));
}輸出
2
更新於: 2021年8月17日
瀏覽量 170
廣告