较小的三数之和
难度:
标签:
题目描述
代码结果
运行时间: 44 ms, 内存: 16.5 MB
/*
题目思路：
给定一个数组nums和一个目标值target，找出数组中三个不同元素的组合，使它们的和小于目标值。
使用Java Stream，我们将数组转换为一个IntStream，然后使用多重嵌套来处理组合问题。
由于Stream不直接支持组合操作，我们需要转换成boxed的形式并处理集合。
*/
import java.util.Arrays;
import java.util.stream.IntStream;
public class Solution {
public long threeSumSmaller(int[] nums, int target) {
Arrays.sort(nums); // 先对数组进行排序
return IntStream.range(0, nums.length - 2) // 遍历第一个元素
.mapToLong(i -> IntStream.range(i + 1, nums.length - 1) // 遍历第二个元素
.mapToLong(j -> IntStream.range(j + 1, nums.length) // 遍历第三个元素
.filter(k -> nums[i] + nums[j] + nums[k] < target) // 过滤符合条件的组合
.count()) // 计数符合条件的组合数量
.sum()) // 汇总第二层循环的计数
.sum(); // 汇总第一层循环的计数
}
}解释
方法:
这个题解使用了排序加双指针的方法来解决问题。首先，将输入数组排序，这样可以更容易地使用双指针来找出满足条件的三元组。对于数组中的每一个元素`c`，使用两个指针`p1`和`p2`，分别指向`c`后面的第一个元素和数组的最后一个元素。通过移动这两个指针来寻找所有满足`nums[p1] + nums[p2] < target - c`的元素对。如果找到这样的对，那么`p1`到`p2`之间的所有元素都可以与`c`组合满足条件，因为数组已经排序。因此，直接将`p2-p1`加到结果中，并将`p1`向右移动查找新的组合。如果不满足条件，则将`p2`向左移动，减小总和。
时间复杂度:
O(n^2)
空间复杂度:
O(1)
代码细节讲解
🦆
为什么在这个算法中选择对数组进行排序？
▷🦆
在算法的执行过程中，如何确保在移动指针后，组合仍然满足条件`nums[p1] + nums[p2] < target - c`？
▷🦆
请问`ret += p2 - p1`这一步骤是如何计算出所有有效组合的数量的？能否详细解释其逻辑？
▷相关问题
三数之和
给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请
你返回所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。
示例 1：
输入：nums = [-1,0,1,2,-1,-4] 输出：[[-1,-1,2],[-1,0,1]] 解释： nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。 nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。 nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。 不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。 注意，输出的顺序和三元组的顺序并不重要。
示例 2：
输入：nums = [0,1,1] 输出：[] 解释：唯一可能的三元组和不为 0 。
示例 3：
输入：nums = [0,0,0] 输出：[[0,0,0]] 解释：唯一可能的三元组和为 0 。
提示：
3 <= nums.length <= 3000-105 <= nums[i] <= 105
最接近的三数之和
给你一个长度为 n 的整数数组 nums 和 一个目标值 target。请你从 nums 中选出三个整数，使它们的和与 target 最接近。
返回这三个数的和。
假定每组输入只存在恰好一个解。
示例 1：
输入：nums = [-1,2,1,-4], target = 1 输出：2 解释：与 target 最接近的和是 2 (-1 + 2 + 1 = 2) 。
示例 2：
输入：nums = [0,0,0], target = 1 输出：0
提示：
3 <= nums.length <= 1000-1000 <= nums[i] <= 1000-104 <= target <= 104