020/qwen2020.github.io

/2021/03/25/022152.html
# 2021-03-25

2021-03-25

2021-03-25 22:55:16

题目

  • 题目：给定一个包含 n 个整数的数组 nums 和一个整数目标值 target。找出 nums 中的三个整数，使得它们的和与目标值最接近。返回这三个整数的和。你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。
  • 示例：
- 输入：nums = [-1,2,1,-4], target = 1 - 输出：2 - 解释：与目标值最接近的和是 2 (-1 + 2 + 1 = 2)。

方法一：暴力解法

  • 时间复杂度：O(n^3)
  • 空间复杂度：O(1)

```java
class Solution {
public int threeSumClosest(int[] nums, int target) {
int result = 0x3f3f3f3f;
int len = nums.length;
for (int i = 0; i < len - 2; i++) {
for (int j = i + 1; j < len - 1; j++) {
for (int k = j + 1; k < len; k++) {
int tmp = nums[i] + nums[j] + nums[k];
if (Math.abs(target - tmp) < Math.abs(target - result)) {
result = tmp;
}
}
}
}
return result;
}
}
```

方法二：排序 + 双指针

  • 时间复杂度：O(n^2)
  • 空间复杂度：O(1)

```java
class Solution {
public int threeSumClosest(int[] nums, int target) {
Arrays.sort(nums);
int len = nums.length, result = 0x3f3f3f3f;
for (int i = 0; i < len - 2; i++) {
int left = i + 1, right = len - 1;
while (left < right) {
int tmp = nums[i] + nums[left] + nums[right];
if (Math.abs(tmp - target) < Math.abs(result - target)) {
result = tmp;
}
if (tmp < target) {
left++;
} else if (tmp > target) {
right--;
} else {
return target;
}
}
}
return result;
}
}
```

方法三：双指针 + 剪枝

  • 时间复杂度：O(n^2)
  • 空间复杂度：O(1)

```java
class Solution {
public int threeSumClosest(int[] nums, int target) {
Arrays.sort(nums);
int len = nums.length, result = 0x3f3f3f3f;
for (int i = 0; i < len - 2; i++) {
int left = i + 1, right = len - 1;
while (left < right) {
int tmp = nums[i] + nums[left] + nums[right];
if (tmp < target) {
if (Math.abs(tmp - target) < Math.abs(result - target)) {
result = tmp;
}
left++;
} else if (tmp > target) {
if (Math.abs(tmp - target) < Math.abs(result - target)) {
result = tmp;
}
right--;
} else {
return target;
}
}
}
return result;
}
}
```

方法四：哈希表

  • 时间复杂度：O(n^2)
  • 空间复杂度：O(n)

```java
class Solution {
public int threeSumClosest(int[] nums, int target) {
Arrays.sort(nums);
Set<Integer> set = new HashSet<>();
int len = nums.length;
int result = 0x3f3f3f3f;
for (int i = 0; i < len - 2; i++) {
set.clear();
for (int j = i + 1; j < len - 1; j++) {
if (set.contains(target - nums[i] - nums[j])) {
int tmp = nums[i] + nums[j] + nums[set.get(target - nums[i] - nums[j])];
if (Math.abs(tmp - target) < Math.abs(result - target)) {
result = tmp;
}
} else {
set.add(nums[j]);
}
}
}
return result;
}
}
```

/2021/03/22/022151.html
# 2021-03-22

2021-03-22

2021-03-22 23:23:38

题目

  • 题目：给定一个整数数组 nums 和一个整数目标值 target。请你找出数组中和为目标值的那两个整数，并返回它们的数组下标。
  • 注意：数组中同一个元素不能使用两遍。
  • 示例：
- 输入：