16. 3Sum Closest
C# 解法
照合済み/オリジナルpublic class Solution {
public int ThreeSumClosest(int[] nums, int target) {
if(nums.Length < 3)
return 0;
Array.Sort(nums);
int start = 0;
int left = 1;
int right = nums.Length - 1;
int direction = nums[start] + nums[left] + nums[right] > 0 ? 1 : 0;
int minDistance = int.MaxValue;
int sum = int.MinValue;
while (start < nums.Length - 2)
{
while (left < right)
{
int currSum = nums[start] + nums[left] + nums[right];
if ( currSum == target )
return target;
if (currSum < target)
left++;
else
right--;
if (Math.Abs(currSum - target) < minDistance)
{
sum = currSum;
minDistance = Math.Abs(currSum - target);
}
}
start ++;
left = start + 1;
right = nums.Length - 1;
}
return sum;
}
}C++ 解法
自動ドラフト、提出前に確認#include <bits/stdc++.h>
using namespace std;
// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
public int ThreeSumClosest(vector<int>& nums, int target) {
if(nums.size() < 3)
return 0;
sort(nums.begin(), nums.end());
int start = 0;
int left = 1;
int right = nums.size() - 1;
int direction = nums[start] + nums[left] + nums[right] > 0 ? 1 : 0;
int minDistance = int.MaxValue;
int sum = int.MinValue;
while (start < nums.size() - 2)
{
while (left < right)
{
int currSum = nums[start] + nums[left] + nums[right];
if ( currSum == target )
return target;
if (currSum < target)
left++;
else
right--;
if (abs(currSum - target) < minDistance)
{
sum = currSum;
minDistance = abs(currSum - target);
}
}
start ++;
left = start + 1;
right = nums.size() - 1;
}
return sum;
}
}Java 解法
照合済み/オリジナルclass Solution {
public int threeSumClosest(int[] nums, int target) {
int n = nums.length;
int closest = 0;
// int min = Integer.MAX_VALUE;
int max = Integer.MAX_VALUE;
Arrays.sort(nums);
//target += 1;
for(int i=0; i<n-2; i++){
int j=i+1;
int k = n-1;
// min = Math.min(min,max);
while(j<k){
int sum = nums[i] + nums[j] + nums[k];
if(sum == target)
return sum;
else if(sum < target)
j++;
else
k--;
int diff = Math.abs(sum - target);
if(diff < max){
max = diff;
closest = sum;
}
}
}
return closest;
}
}JavaScript 解法
照合済み/オリジナル/**
* @param {number[]} nums
* @param {number} target
* @return {number}
*/
var threeSumClosest = function (nums, target) {
nums.sort((a, b) => a - b);
let ans = 1 << 30;
const n = nums.length;
for (let i = 0; i < n; ++i) {
let j = i + 1;
let k = n - 1;
while (j < k) {
const t = nums[i] + nums[j] + nums[k];
if (t === target) {
return t;
}
if (Math.abs(t - target) < Math.abs(ans - target)) {
ans = t;
}
if (t > target) {
--k;
} else {
++j;
}
}
}
return ans;
};Python 解法
照合済み/オリジナルclass Solution:
def threeSumClosest(self, num, target):
num.sort()
result = num[0] + num[1] + num[2]
for i in range(len(num) - 2):
j, k = i+1, len(num) - 1
while j < k:
sum = num[i] + num[j] + num[k]
if sum == target:
return sum
if abs(sum - target) < abs(result - target):
result = sum
if sum < target:
j += 1
elif sum > target:
k -= 1
else:
return result
return resultGo 解法
照合済み/オリジナルfunc threeSumClosest(nums []int, target int) int {
sort.Ints(nums)
var ans int
diff:=math.MaxInt
for i:=0;i<len(nums)-2;i++{
low:=i+1
high:=len(nums)-1
for low<high{
if nums[i]+nums[low]+nums[high]==target{
ans=target
return ans
}else if int(math.Abs(float64(nums[i]+nums[low]+nums[high]-target)))<diff{
diff=int(math.Abs(float64(nums[i]+nums[low]+nums[high]-target)))
ans=nums[i]+nums[low]+nums[high]
}
if nums[i]+nums[low]+nums[high]>target{
high--
}else{
low++
}
}
}
return ans
}Проверка длины 配列а:
Сначала проверяется, содержит ли 配列 nums хотя бы три elementа. Если нет, метод returns 0, так как нет смысла искать сумму трёх elementов.
Сортировка 配列а:
配列 nums сортируется. Это необходимо для упрощения поиска комбинаций с использованием двух указателей.
Инициализация переменных:
start инициализируется на первом elementе, left на втором, и right на последнем elementе 配列а.
Переменные direction, minDistance, и sum инициализируются для отслеживания минимального расстояния до целевой суммы и самого близкого найденного значения суммы.
Внешний цикл:
Внешний цикл перебирает elementы 配列а начиная с первого. Для каждого elementа start он рассматривает комбинации elementов с использованием двух других указателей (left и right).
Внутренний цикл:
Внутренний цикл выполняется до тех пор, пока указатели left и right не пересекутся.
Рассчитывается сумма elementов, на которые указывают указатели start, left, и right.
Если сумма совпадает с целевой суммой, returnsся целевая сумма, так как это идеальный случай.
Обновление указателей и значений:
Если сумма меньше целевой, left сдвигается вправо (увеличивается), чтобы увеличить сумму.
Если сумма больше целевой, right сдвигается влево (уменьшается), чтобы уменьшить сумму.
При каждом изменении указателей обновляется минимальное расстояние между текущей суммой и целевой суммой, если новое расстояние меньше текущего.
Возвращение результата:
После завершения всех итераций returnsся значение sum, которое является суммой трех elementов, ближайшей к целевой сумме.
Временная и пространственная Complexity:
Временная Complexity: O(n^2), где n — количество elementов в 配列е. Основная Complexity обусловлена двойным перебором elementов 配列а (внешний цикл и внутренний цикл).
Пространственная Complexity: O(1), так как используется фиксированное количество переменных для хранения данных и индексов, не зависящих от размера 入力ных данных.
Vacancies for this task
有効な求人 with overlapping task tags are 表示.