本文主要是介绍运行了一晚上的经典京东面试原题,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
写在前面
今天在「京东」题库中翻到一道经典题。
众所周知,题目越经典,评论区越逆天。
说归说,闹归闹,这道题还是要掌握的。
毕竟除了京东,汇量科技也在测试开发中考过:
下面一起来看看吧 ~
题目描述
平台:LeetCode
题号:16
给定一个包括 个整数的数组 nums
和 一个目标值 target
。
找出 nums
中的三个整数,使得它们的和与 target
最接近。
返回这三个数的和。
每组输入只存在唯一答案。
示例:
输入:nums = [-1,2,1,-4], target = 1
输出:2
解释:与 target 最接近的和是 2 (-1 + 2 + 1 = 2) 。
提示:
排序 + 双指针
对数组进行排序,使用三个指针 i
、j
和 k
分别代表要找的三个数。
-
通过枚举
i
确定第一个数,另外两个指针j
,k
分别从左边i + 1
和右边n - 1
往中间移动,找到满足nums[i] + nums[j] + nums[k]
最接近target
的唯一解。 -
j
和k
指针的移动逻辑,分情况讨论sum = nums[i] + nums[j] + nums[k]
:-
sum
>target
:k
左移,使sum
变小 -
sum
<target
:j
右移,使sum
变大 -
sum
=target
:找到最符合要求的答案,直接返回
-
为了更快找到答案,对于相同的 i
,可以直接跳过下标。
Java 代码:
class Solution {
public int threeSumClosest(int[] nums, int target) {
Arrays.sort(nums);
int n = nums.length, ans = nums[0] + nums[1] + nums[2];
for (int i = 0; i < n; i++) {
if (i > 0 && nums[i] == nums[i - 1]) continue;
int j = i + 1, k = n - 1;
while (j < k) {
int sum = nums[i] + nums[j] + nums[k];
if (Math.abs(sum - target) < Math.abs(ans - target)) ans = sum;
if (ans == target) {
return target;
} else if (sum > target) {
k--;
} else if (sum < target) {
j++;
}
}
}
return ans;
}
}
C++ 代码:
class Solution {
public:
int threeSumClosest(vector<int>& nums, int target) {
sort(nums.begin(), nums.end());
int n = nums.size(), ans = nums[0] + nums[1] + nums[2];
for (int i = 0; i < n; i++) {
if (i > 0 && nums[i] == nums[i - 1]) continue;
int j = i + 1, k = n - 1;
while (j < k) {
int sum = nums[i] + nums[j] + nums[k];
if (abs(sum - target) < abs(ans - target)) ans = sum;
if (ans == target) {
return target;
} else if (sum > target) {
k--;
} else if (sum < target) {
j++;
}
}
}
return ans;
}
};
Python 代码:
class Solution:
def threeSumClosest(self, nums: List[int], target: int) -> int:
nums.sort()
n, ans = len(nums), nums[0] + nums[1] + nums[2]
for i in range(n):
if i > 0 and nums[i] == nums[i - 1]:
continue
j, k = i + 1, n - 1
while j < k:
s = nums[i] + nums[j] + nums[k]
if abs(s - target) < abs(ans - target):
ans = s
if ans == target:
return target
elif s > target:
k -= 1
elif s < target:
j += 1
return ans
TypeScript 代码:
function threeSumClosest(nums: number[], target: number): number {
nums.sort((a, b) => a - b);
let n = nums.length, ans = nums[0] + nums[1] + nums[2];
for (let i = 0; i < n; i++) {
if (i > 0 && nums[i] == nums[i - 1]) continue;
let j = i + 1, k = n - 1;
while (j < k) {
const sum = nums[i] + nums[j] + nums[k];
if (Math.abs(sum - target) < Math.abs(ans - target)) ans = sum;
if (ans == target) {
return target;
} else if (sum > target) {
k--;
} else if (sum < target) {
j++;
}
}
}
return ans;
};
-
时间复杂度:排序的复杂度为 ,对于每个 i
而言,最坏的情况j
和k
都要扫描一遍数组的剩余部分,复杂度为 。整体复杂度为 -
空间复杂度:
更多更全更热门的「笔试/面试」相关资料可访问排版精美的 合集新基地 🎉🎉
这篇关于运行了一晚上的经典京东面试原题的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!