1.题目描述
(1) 三数之和
给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？找出所有满足条件且不重复的三元组。
注意：答案中不可以包含重复的三元组。
示例：
给定数组 nums = [-1, 0, 1, 2, -1, -4]，
满足要求的三元组集合为：
[
[-1, 0, 1],
[-1, -1, 2]
]
(2)最接近的三数之和
给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数，使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。
例如，给定数组 nums = [-1，2，1，-4], 和 target = 1.
与 target 最接近的三个数的和为 2. (-1 + 2 + 1 = 2).
2.思路分析
1.在一个数组中找一个数：搜索，二分查找（时间复杂度O(N)）
2.在一个数组中找两个数：LeetCode_01两数之和问题，LeetCode_11盛最多水的容器（时间复杂度O(N)）
两种思路：
①用HashMap或者HashSet来存储已经遍历的，空间换时间
②双指针，通过移动两个指针来遍历
3.在一个数组中找三个数：LeetCode_15三数之和，LeetCode_16最接近的三数之和
通常的处理步骤：
（1）将当前数组排序，时间复杂度O(NlogN)
（2）选一个固定值，再双指针遍历。时间复杂度O(N^2)
本题的详细思路
①首先进行数组排序，Arrays.sort()
②在数组 nums 中，进行遍历，每遍历一个值利用其下标i，形成一个固定值 nums[i]
③再使用前指针指向 start = i + 1 处，后指针指向 end = nums.length - 1 处，也就是结尾处
④根据 sum = nums[i] + nums[start] + nums[end] 的结果，判断 sum 与目标 target 的距离，如果更近则更新结果 ans
⑤同时判断 sum 与 target 的大小关系，因为数组有序，如果 sum > target 则 end--，如果 sum < target 则 start++，如果 sum == target 则说明距离为 0 直接返回结果
3.代码实现
三数之和：
package part2;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
/**
* @author haiboWu
* @create 2020-02-03 10:44
*/
public class No_15 {
public static void main(String[] args) {
int nums[] = {-4, -2, 1, -5, -4, -4, 4, -2, 0, 4, 0, -2, 3, 1, -5, 0};
System.out.println(threeSum(nums));
}
public static List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> lists = new ArrayList<>();
int len = nums.length;
if (nums == null || len < 3) return lists;
Arrays.sort(nums);
for (int i = 0; i < len; i++) {
if (i > 0 && nums[i] == nums[i - 1]) continue;
if (nums[i] > 0) break;
int l = i + 1, r = len - 1;
while (l < r) {
int sum = nums[i] + nums[l] + nums[r];
if (sum == 0) {
while (l < r && nums[l] == nums[l + 1]) l++;
while (l < r && nums[r] == nums[r - 1]) r--;
ArrayList<Integer> list = new ArrayList<>();
list.add(nums[i]);
list.add(nums[l]);
list.add(nums[r]);
lists.add(list);
l++;
r--;
} else if (sum > 0) {
r--;
} else {
l++;
}
}
}
return lists;
}
}
最接近的三数之和
package part2;
import java.util.Arrays;
/**
* @author haiboWu
* @create 2020-02-03 17:13
*/
public class No_16 {
public static void main(String[] args) {
int nums[] = {-1, 2, 1, -4};
System.out.println(threeSumClosest(nums, 1));
}
public static int threeSumClosest(int[] nums, int target) {
int len = nums.length;
int sum = nums[0] + nums[1] + nums[2];
int ans = sum;
Arrays.sort(nums);
for (int i = 0; i < len; i++) {
int l = i + 1, r = len - 1;
while (l < r) {
sum = nums[i] + nums[l] + nums[r];
if(Math.abs(ans-target)>Math.abs(sum-target)){
ans=sum;
}
if (sum == target) return target;
if (sum > target) {
r--;
} else {
l++;
}
}
}
return ans;
}
}
