資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
JavaScript
PHP
物理
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚學
法律研究如何使用 C# 查詢接近目標的四元組？
雙指標模式類似於四元組求和為零。我們可以採用類似的方法遍歷陣列，一次取一個數字。在每個步驟中，我們將儲存四元組和目標數之間的差，並在每個步驟將其與迄今為止的最小目標差進行比較，以便在最後，我們可以返回最接近總和的三元組。
時間複雜度
對陣列進行排序需要 O(N* logN)。總體而言，fourSumClosest() 將需要 O(N * logN + N^3)，這在漸進意義上等效於 O(N^3)。
空間複雜度
上述演算法的空間複雜度為 O(N)，這是排序所需的。
示例
public class Arrays{
public int FourSumClosestToTarget(int[] nums, int target){
if (nums == null || nums.Length == 0){
return -1;
}
int[] newNums = nums.OrderBy(x => x).ToArray();
int initialSum = newNums[0] + newNums[1] + newNums[2] + newNums[3];
for (int i = 0; i < nums.Length; i++){
for (int j = i; j < nums.Length; j++){
int left = j + 1;
int right = nums.Length - 1;
while (left < right){
int nearestSum = newNums[i] + newNums[j] + newNums[left] + newNums[right];
if (nearestSum < initialSum){
initialSum = nearestSum;
}
if (nearestSum == target){
return nearestSum;
}
else if (nearestSum < target){
left++;
}
else{
right--;
}
}
}
}
return initialSum;
}
}
static void Main(string[] args){
Arrays s = new Arrays();
int[] nums = { 1,0,-1,0,-2,2 };
var ss = FourSumClosestToTarget(nums,0);
Console.WriteLine(ss);
}輸出
0
更新時間：17-8-2021
99 次瀏覽
廣告