資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究C++ 中的最接近的 3Sum
假設有一個包含 n 個整數和一個目標值 target 的陣列 nums。我們必須在 nums 中找到三個整數，使得它們的和最接近於目標值。我們將返回這三個整數的和。我們可以假設每個輸入都恰好有一個解。所以如果給定的陣列像 [-1,2,1,-4] 目標值為 1，那麼三元組將是 [-1,2,1]，它具有最接近的和，即 2。
為了解決這個問題，我們將遵循以下步驟：-
- 對陣列 nums 進行排序，ans := 0，diff := 無窮大，n := nums 的大小
- 對於從 0 到 n-1 的區間內的 i
- left := i + 1，right := n – 1
- 當 left < right
- temp := nums[left] + nums[right] + nums[i]
- 如果 |target - temp| < diff，那麼 ans := temp，diff := |target - temp|
- 如果 temp = target，那麼返回 temp，否則當 temp > target 時，right 減 1，否則 left 加 1
- 返回 ans
示例 (C++)
讓我們看看以下實現以獲得更深入的瞭解：-
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int threeSumClosest(vector<int>& nums, int target) {
sort(nums.begin(), nums.end());
int ans = 0;
int diff = INT_MAX;
int n = nums.size();
for(int i = 0; i < n; i++){
int left = i + 1;
int right = n - 1;
while(left < right){
int temp = nums[left] + nums[right] + nums[i];
if(abs(target - temp) < diff){
ans = temp;
diff = abs(target - temp);
}
if(temp == target)return temp;
else if(temp > target) right--;
else left++;
}
}
return ans;
}
};
main(){
Solution ob;
vector<int> v = {-1,2,1,-4};
cout << ob.threeSumClosest(v, 1);
}輸入
[-1,2,1,-4] 1
輸出
2
更新於: 2020 年 4 月 27 日
1000 多次瀏覽
廣告