สมมติว่าเรามีจำนวนอาร์เรย์ที่มีจำนวนเต็ม n และหนึ่งเป้าหมาย เราต้องหาจำนวนเต็มสามจำนวนเป็น num เพื่อให้ผลรวมใกล้เคียงกับเป้าหมายมากที่สุด เราจะคืนค่าผลรวมของจำนวนเต็มสามจำนวน เราสามารถสันนิษฐานได้หนึ่งข้อว่าแต่ละอินพุตจะมีทางออกเดียว ดังนั้นหากอาร์เรย์ที่กำหนดเป็นเหมือน [-1,2,1,-4] และเป้าหมายคือ 1 ดังนั้นแฝดสามจะเป็น [-1,2,1] ซึ่งมีผลรวมใกล้เคียงที่สุด นั่นคือ 2
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- จัดเรียง nums อาร์เรย์, ans :=0, diff :=Infinity, n :=ขนาดของ nums
- สำหรับ i ในช่วง 0 ถึง n – 1
- ซ้าย :=i + 1, ขวา :=n – 1
- ขณะซ้าย <ขวา
- อุณหภูมิ :=nums[left] + nums[right] + nums[i]
- ถ้า |เป้าหมาย – ชั่วคราว|
- ถ้า temp =target ให้คืนค่า temp มิฉะนั้น เมื่อ temp> target จากนั้นลดทางขวา 1 มิฉะนั้น จะเพิ่มไปทางซ้าย 1
- คืนสินค้า
ตัวอย่าง(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
