[LeetCode#16]3 Sum Closest(最も近い3数の和)
7053 ワード
問題の説明
n個の要素を有する整数配列numsと1つの整数targetを与え、nums中の3つの要素a、b、cを探し出し、a+b+cがtargetに最も近い距離になり、この最も近い距離を出力する.Example:nums＝［−1,2,1,−4］,target＝1 Result:2,ここで−1＋2＋1＝2が最も近い.
解決策
この問題はLeetCode 15問題と似ていますが、違いもあります.まず最も考えやすいのは3層サイクルで、3つの数を取って毎回距離を加算して判断し、それから最短距離のグループとを探しますが、この方法は通用せず、深刻なタイムアウトになります.以下,LeetCode 15の手法と結びつけて,配列を先に並べ替えることを考慮し,2層のループだけで完了する.具体的な方法は以下の通りである:第一歩はまず配列を並べ替えて、ここで直接並べ替え関数を呼び出して、Arrays.sort(nums); 第2のステップの外側の1層のループは1つの要素nums[i]を取り出すたびに、中には2つのポインタでleftとrightを識別し、leftはi+1要素を指し始め、rは最後の要素を指す.次にsum=nums[i]+nums[left]+nums[right]を三数で加算し、targetと距離を判断する:——>sum=target距離が0であれば、直接結果をsumに返す.——>sum>targetの場合、説明とsumが大きい場合、right=right-1は左に小さい数を探します.——>sumコード実装
n個の要素を有する整数配列numsと1つの整数targetを与え、nums中の3つの要素a、b、cを探し出し、a+b+cがtargetに最も近い距離になり、この最も近い距離を出力する.Example:nums＝［−1,2,1,−4］,target＝1 Result:2,ここで−1＋2＋1＝2が最も近い.
解決策
この問題はLeetCode 15問題と似ていますが、違いもあります.まず最も考えやすいのは3層サイクルで、3つの数を取って毎回距離を加算して判断し、それから最短距離のグループとを探しますが、この方法は通用せず、深刻なタイムアウトになります.以下,LeetCode 15の手法と結びつけて,配列を先に並べ替えることを考慮し,2層のループだけで完了する.具体的な方法は以下の通りである:第一歩はまず配列を並べ替えて、ここで直接並べ替え関数を呼び出して、Arrays.sort(nums); 第2のステップの外側の1層のループは1つの要素nums[i]を取り出すたびに、中には2つのポインタでleftとrightを識別し、leftはi+1要素を指し始め、rは最後の要素を指す.次にsum=nums[i]+nums[left]+nums[right]を三数で加算し、targetと距離を判断する:——>sum=target距離が0であれば、直接結果をsumに返す.——>sum>targetの場合、説明とsumが大きい場合、right=right-1は左に小さい数を探します.——>sum
import java.util.Arrays;
class Solution {
public int threeSumClosest(int[] nums, int target) {
Arrays.sort(nums); //
int result = nums[0] + nums[1] + nums[nums.length - 1];
for(int i=0; i < nums.length; i++){
int left = i + 1;
int right = nums.length - 1;
while(left < right){
int sum = nums[i] + nums[left] + nums[right];
if(sum == target){ // target
return target;
}else{
int dis = Math.abs(sum - target);
int temp = Math.abs(result - target);
if(dis < temp){ // target
result = sum;
}
if(sum > target){ // target ，
right--;
}
else{ // target ，
left++;
}
}
}
}
return result;
}
}