题目选自力扣第16题：
最接近的三数之和
c#与java代码书写的主要差别就是c#方法名首字母大写，java方法名首字母小写，c#属性名大写，java属性名小写。
方法一的C#实现：执行用时 252ms
public class Solution {
public int ThreeSumClosest(int[] nums, int target) {
// 排序
Array.Sort(nums);
int closestNum = nums[0] + nums[1] + nums[2];
for (int i = 0; i < nums.Length - 2; i++)
{
int l = i + 1, r = nums.Length - 1;
while (l < r)
{
int threeSum = nums[l] + nums[r] + nums[i];
if (Math.Abs(threeSum - target) < Math.Abs(closestNum - target))
{
closestNum = threeSum;
}
if (threeSum > target)
{
r--;
}
else if (threeSum < target)
{
l++;
}
else
{
// 如果已经等于target的话, 肯定是最接近的
return target;
}
}
}
return closestNum;
}
}
方法一的java实现： 执行用时 27ms
class Solution {
public int threeSumClosest(int[] nums, int target) {
// 排序
Arrays.sort(nums);
int closestNum = nums[0] + nums[1] + nums[2];
for (int i = 0; i < nums.length - 2; i++)
{
int l = i + 1, r = nums.length - 1;
while (l < r)
{
int threeSum = nums[l] + nums[r] + nums[i];
if (Math.abs(threeSum - target) < Math.abs(closestNum - target))
{
closestNum = threeSum;
}
if (threeSum > target)
{
r--;
}
else if (threeSum < target)
{
l++;
}
else
{
// 如果已经等于target的话, 肯定是最接近的
return target;
}
}
}
return closestNum;
}
}
方法二的C#实现：执行用时324ms
public class Solution {
public int ThreeSumClosest(int[] nums, int target) {
int sumLength = nums.Length * (nums.Length - 1) * (nums.Length - 2) / 6;
int[] sum = new int[sumLength];
int sumKey = 0;
int[] sumDiff = new int[sumLength];
int minNum = 0;
for (int i = 0; i < nums.Length - 2; i++)
{
for (int j = i + 1; j < nums.Length - 1; j++)
{
for (int k = j + 1; k < nums.Length; k++)
{
sum[sumKey] = nums[i] + nums[j] + nums[k];
sumDiff[sumKey] = System.Math.Abs(sum[sumKey] - target);
if (sumDiff[sumKey] == 0)
{
return sum[sumKey];
}
if (sumDiff[sumKey] < sumDiff[minNum])
{
minNum = sumKey;
}
sumKey++;
}
}
}
return sum[minNum];
}
}
方法二的java实现： 执行用时 110ms
class Solution {
public int threeSumClosest(int[] nums, int target) {
int sumLength = nums.length * (nums.length - 1) * (nums.length - 2) / 6;
int[] sum = new int[sumLength];
int sumKey = 0;
int[] sumDiff = new int[sumLength];
int minNum = 0;
for (int i = 0; i < nums.length - 2; i++)
{
for (int j = i + 1; j < nums.length - 1; j++)
{
for (int k = j + 1; k < nums.length; k++)
{
sum[sumKey] = nums[i] + nums[j] + nums[k];
sumDiff[sumKey] = Math.abs(sum[sumKey] - target);
if (sumDiff[sumKey] == 0)
{
return sum[sumKey];
}
if (sumDiff[sumKey] < sumDiff[minNum])
{
minNum = sumKey;
}
sumKey++;
}
}
}
return sum[minNum];
}
}
C++实现：执行用时8ms
class Solution {
public:
int threeSumClosest(vector<int>& nums, int target) {
int res = 0;
if(nums.size() < 3) return res;
res = nums[0] + nums[1] + nums[2];
sort(nums.begin(), nums.end());
for(int i = 0; i < nums.size(); ++i){
int l = 0, r = nums.size() - 1;
while(l < r){
if(l == i || r == i) break;
res = abs(res - target) < abs(nums[l] + nums[r] - target + nums[i]) ? res : nums[l] + nums[r] + nums[i];
if(nums[l] + nums[r] == target - nums[i]) return target;
else if(nums[l] + nums[r] < target - nums[i]) ++l;
else --r;
}
}
return res;
}
};
Python3实现：执行用时124ms
class Solution:
def threeSumClosest(self, nums, target):
nums.sort()
res = None
i = 0
for i in range(len(nums)):
if i == 0 or nums[i] > nums[i-1]:
l = i+1
r = len(nums)-1
while l < r:
s = nums[i] + nums[l] + nums[r]
res = s if res == None or abs(
s-target) < abs(res-target) else res
if s == target:
return s
elif s > target:
r -= 1
else:
l += 1
return res
js实现：执行用时216ms
var threeSumClosest = function(nums, target) {
nums.sort(function(a, b) {
return a - b
})
let res = nums[0] + nums[1] + nums[2]
let cur = 0
let diff = Math.abs(nums[0] + nums[1] + nums[2] -target)
for(let i=0;i<nums.length - 2; i++) {
let j = i + 1
let k = nums.length - 1
while(j<k) {
cur = nums[i] + nums[j] + nums[k]
if(Math.abs(cur - target) < diff) {
diff = Math.abs(cur - target)
res = cur
}
if(cur < target) {
j++
} else {
k--
}
}
}
return res
};
最后将力扣上各语言实现的总体执行耗时情况按执行效率从高到低排序如下：
微信图片_20190118165457.jpg
网友评论