代码随想录刷题day20|（哈希表篇）15.三数之和
目录
一、哈希表理论基础
二、题目思路及难点
三、相关算法题目
四、相关知识点
一、哈希表理论基础
详见 代码随想录刷题day15|（哈希表篇）242.有效的字母异位词、383.赎金信-CSDN博客
二、题目思路及难点
本题的三元组不可以重复，涉及到去重，如果用哈希法比较麻烦，所以用双指针法；
思路：首先对数组进行排序，因为题目要求具体三元组 而非 下标，所以可以对数组进行排序，如果要返回下标，则排序后下标就乱了；
接着定义两个指针left和right，遍历数组，变量 i 从第一个元素开始，left初始指向第 i+1 个元素，right 初始指向第 nums.length - 1 个数组元素，题目要求三数之和，这里 i 代表a，left 代表b，right 代表 c，那么a+b+c 即 nums[i] + nums[left] + nums[right]，记为sum，判断的逻辑为：如果sum > 0，则 right--；如果sum < 0，则left++；如果 sum = 0；则获得对应结果；
以上为整体思路，在其中还要对a b c去重，注意：求的是不能重复的三元组，但是三元组中的元素是可以重复的；
对a去重时，判断:nums[i] == nums[i-1]，同时保证 i > 0，否则 nums[i - 1] 为空；
对b和c去重，分别判断：nums[left] == nums[left + 1]、nums[right] == nums[right - 1]，如果相等，那么left++，right--；
首先对a去重，接着判断sum大小，得到一个有效结果以后，再对b c去重，最后更新left和right的值时，应该在内层循环；如果放在外面 相当于 判断完sum， left/right已经更新一次，然后再同时更新一次，就会出错；
难点
Q：对a去重为什么不是判断 nums[i] == nums[i+1]？
A：如果判断nums[i] == nums[i+1]，i+1是left，即判断结果中某一个具体三元组里能否有重复元素，由前可知，三元组中允许有重复元素；
判断nums[i] == nums[i-1]的话，即判断nums[i]和前一个元素是否相等，假设有三元组[-1,-1,2]，当 i 遍历到第一个-1的位置时，和前一个位置的元素相比，就是和上一次遍历（循环）中a位置（i代表a，a+b+c）的 i 的取值进行比较，是比较当前的a和之前做过a的数（nums[i-1]）也就是同一“岗位”去重；
如果和前一位置的数一样，那么对于相同的left和right来说，判断sum的结果是相同的，得到的结果也就相同，即重复三元组；
遍历nums[i-1]时已经把nums[i-1]的所有和为0的对应三元组都查找到了，所以如果nums[i]和nums[i-1]相等，那么遍历nums[i]时，就应该跳过，这样才能达到对a去重的效果；
Q：对b、c去重的逻辑？
A：对b：如果nums[left]和nums[left+1]相同，
Q：对b、c去重能放在判断sum之前吗？
A：假设数组为[0,0,0,0,0]，nums[i]、nums[left]、nums[right]相同，先对b、c去重的话，left和right就会不断更新，最终left = right，退出while，但实际本数组有符合要求的三元组，所以不能放在判断sum之前，要放在得到一个结果之后；
Q：为什么不是while(left <= right)？
A：边界问题，代入判断，当left = right > b = c，指向同一个数，结果就为二元组，且题中要求 i、j、k互不相等，即三个索引不等，所以left = right 不符题意；
Q：left和right如何移动？
A：根据sum，sum > 0，则 right--；sum < 0，则left++；sum = 0；则获得对应结果；
Q：最后更新left、right时能只更新一个吗？
A：不能，假设此时得到和为0的结果，如果只改变left，left++，相当于在0的基础上，三数 之和sum变大（数组有序），同理只变right--，sum变小，只有同时改变，sum才有可能为0；
三、相关算法题目
15.三数之和
15. 三数之和 - 力扣（LeetCode）
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
//定义二维列表
List<List<Integer>> result = new ArrayList<List<Integer>> ();
//ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>> (); ▲ 报错
//对数组排序
Arrays.sort(nums);// ▲
for(int i = 0;i < nums.length;i++){
if(nums[i] > 0){
//数组全为正数 三数之和不可能为0
return result;
}
//对a去重
if(i > 0 && nums[i] == nums[i - 1]){
continue;//结束本次循环
}//i=0 不会continue;nums[i] != nums[i-1] 不会continue;
int left = i + 1; //left right随着i进行更新
int right = nums.length - 1;
while(left < right){
int sum = nums[i] + nums[left] + nums[right];
if(sum < 0){
left++;
}else if(sum > 0){
right--;
}else{
//获得符合条件的三元组 ▲
//将符合条件的a b c添加到result中
result.add(Arrays.asList(nums[i], nums[left], nums[right]));
//对b去重
while(left < right && nums[left] == nums[left + 1]){
left++;
}
//对c去重
while(left < right && nums[right] == nums[right - 1]){
right--;
}
left++;
right--; //不能放在else外 如果放在外面 相当于
//判断完sum left/right已经更新一次 然后再同时更新一次
}
}
}
return result;
}
}四、相关知识点
Arrays概述和常用方法
4.1 概述
Arrays是操作数组的工具类，方法均为静态方法，调用时通过 类名. 调用；
4.2 常用方法
1.toString：将数组变成字符串
2.binarySearch：二分查找法查找元素
使用二分搜索法的前提：数组中的元素必须有序，且为升序；
3.copyOf：拷贝数组
参数1：老数组 参数2：新数组的长度
如果新数组长度 < 老数组长度，根据新数组长度部分拷贝；
如果新数组长度 = 老数组长度，完全拷贝；
如果新数组长度 > 老数组长度，完全拷贝+补上默认初始值（int类型为0）；
4.copyOfRange：拷贝数组（指定范围）
细节：包头不包尾，包左不包右；
5.fill：填充数组
6.sort：排序
默认情况下，给基本数据类型进行升序排列，底层使用的是快速排序；
7.asList：将数组转为集合
用于将一个数组转换为一个固定大小的列表List。该列表不能进行添加或删除操作。
返回的是一个 List<T> 类型的对象，其中 T 是数组元素的类型；T... a：这是一个可变参数，表示可以传入一个数组或多个同类型的参数。
注意点：
-
固定大小：返回的
List是固定大小的，不能进行add()或remove()操作。尝试进行这些操作会抛出UnsupportedOperationException异常。 -
基于数组：返回的
List是基于传入的数组创建的，因此对返回的List进行修改操作（如set()方法）会直接影响原始数组。 -
泛型支持：支持泛型，可以处理任意类型的数组。
4.3 相关代码解释
List<List<Integer>> result = new ArrayList<List<Integer>> ();
result.add(Arrays.asList(nums[i], nums[left], nums[right]));
第一行代码声明了一个 ArrayList，其元素类型是 List<Integer>。换句话说，result 是一个二维列表，每个元素本身也是一个 List<Integer>。
第二行代码调用了 result 的 add 方法，将一个由 Arrays.asList 创建的固定大小的列表添加到 result 中。
-
Arrays.asList返回的是一个固定大小的列表，但它仍然是一个有效的List对象。 -
List的add方法可以添加任何对象，只要这个对象的类型符合List的泛型定义。 -
result是一个二维列表，每个元素本身也是一个List<Integer>，因此可以将Arrays.asList返回的列表作为一个元素添加到result中，相当于添加一个三元组作为第一个元素；