1.三数之和（15 - 中）
题目描述：给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。
示例 :
输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
思路：先排序方便使用双指针查找元素，核心思想是：遍历数组，先用0 - 当前值作为sum，再使用双指针查找剩余两个元素。
注意：
-
对于含有重复元素的情况直接略过，否则会超时。
-
双指针的左边界为
i + 1。
代码实现：
public List<List<Integer>> threeSum(int[] nums) {
Arrays.sort(nums);
List<List<Integer>> ans = new ArrayList<>();
for (int i = 0; i < nums.length - 2; ++i) {
if (i == 0 || (i > 0 && nums[i] != nums[i - 1])) {
int l = i + 1, r = nums.length - 1;
while (l < r) {
int sum = nums[i] + nums[l] + nums[r];
if (sum == 0) {
// 存储结果，数组转集合
ans.add(Arrays.asList(nums[i], nums[l], nums[r]));
// 防止相同的元素加入集合
while (l < r && nums[l] == nums[l + 1]) l++;
while (l < r && nums[r] == nums[r - 1]) r--;
l++;
r--;
} else if (sum > 0) {
r--;
} else {
l++;
}
}
}
}
return ans;
}
2.最接近的三数之和（16 - 中）
题目描述：给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数，使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。
示例 :
输入：nums = [-1,2,1,-4], target = 1
输出：2
解释：与 target 最接近的和是 2 (-1 + 2 + 1 = 2) 。
思路：与上题三数之和基本类似的解法，遍历数组，更新三数之和与目标值最小的差值。
注意：当三数之和等于目标值可以直接返回（最近）。
代码实现：
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 {
return target;
}
}
}
return closestNum;
}
3.较小的三数之和（259 - 中）
题目描述：给定一个长度为 n 的整数数组和一个目标值 target，寻找能够使条件 nums[i] + nums[j] + nums[k] < target 成立的三元组 i, j, k 个数（0 <= i < j < k < n）。
示例 :
输入: nums = [-2,0,1,3], target = 2
输出: 2
解释: 因为一共有两个三元组满足累加和小于 2:
[-2,0,1]
[-2,0,3]
思路：殊途同归，本题寻找小于目标值的三元组的个数。注意：若此时右边界组成的三元组符合条件，那么之前的位置都符合条件。
代码实现：
public int threeSumSmaller(int[] nums, int target) {
Arrays.sort(nums);
int ans = 0;
for (int i = 0; i < nums.length - 2; ++i) {
int l = i + 1, r = nums.length - 1;
while (l < r){
int sum = nums[l] + nums[r] + nums[i];
if (sum >= target) {
r--;
} else {
ans += r - l;
l++;
}
}
}
return ans;
}
4.四数之和（18 - 中）
题目描述：给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组。
注意：答案中不可以包含重复的四元组。
示例 :
输入：nums = [1,0,-1,0,-2,2], target = 0
输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]
思路：本质不变，在三数之和基础上又加了一层循环。还是注意对于重复值的剔除（跳过）。
代码实现：
public List<List<Integer>> fourSum(int[] nums, int target) {
Arrays.sort(nums);
List<List<Integer>> ans = new ArrayList<>();
int n = nums.length;
for (int i = 0; i < n - 3; i++) {
if (i > 0 && nums[i] == nums[i - 1]) continue;
for (int j = i + 1; j < n - 2; j++) {
if (j > i + 1 && nums[j] == nums[j - 1]) continue;
int l = j + 1, r = n - 1;
while (l < r) {
int sum = nums[i] + nums[j] + nums[l] + nums[r];
if (sum == target) {
ans.add(Arrays.asList(nums[i], nums[j], nums[l], nums[r]));
while (l < r && nums[l] == nums[l + 1]) l++;
while (l < r && nums[r] == nums[r - 1]) r--;
l++;
r--;
} else if (sum > target) {
r--;
} else {
l++;
}
}
}
}
return ans;
}
网友评论