Написано: 26.02.2023
16. 3Sum Closest
Задание.
Получен целочисленный массив nums длины n и целочисленное target
Найдите три целых числа в nums таких, чтобы сумма была ближайшей к target.
Возвратить сумму трех целых чисел.
Предполагается, что для любых входных данных есть ровно одно решение.
Пример 1.
Входные данные: nums = [-1,2,1,-4], target = 1
Результат: 2
Пояснение: Сумма, наиболее близкая к target, равна 2. (-1 + 2 + 1 = 2).
Пример 2.
Входные данные: nums = [0,0,0], target = 1
Результат: 0
Пояснение: Сумма, наиболее близкая к target, равна 0. (0 + 0 + 0 = 0).
Решение.
class Solution {
public:
int threeSumClosest(vector<int>& nums, int target) {
int n = nums.size(), diff = INT_MAX, ans = 0, s, e, i, sum;
sort(nums.begin(),nums.end());
for(i = 0; i < n; i++) {
s = i+1;
e = n-1;
while(s < e) {
if((sum = nums[i] + nums[s] + nums[e]) == target) {
return target;
} else if(abs(sum - target) < diff) {
diff = abs(sum - target);
ans = sum;
}
if(sum < target) {
s++;
} else if(sum > target) {
e--;
}
}
}
return ans;
}
};