[15]三数之和
1、题目
给你一个整数数组 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
- 数组
- 双指针
- 排序
2、题目分析
1、三元变量转二元变量：nums[i] + nums[j] + nums[k] = 0 ==> num[j] + num[k] = -num[i]
即确定 num[i] 求 num[j]、num[k]。
2、二元变量求解方案性能优化（暴力解法转双指针）：
找某个状态下，二元变量的联系规则。当num[i]确定时， num[j] 和 num[k] 是负相关关系。
而基于这个负相关关系，我们把数据排好序，就可以运用双指针算法
3、解题步骤
1、对数组排序
2、遍历数组，将每个数指定为 num[i]，再使用双指针扫描下标 i 之后的数据，查找是否存在 num[j] + num[k] = -num[i]
注意：因为三元组不要求顺序且要求不重复，故 num[i] 的值不能重复指定。因为下标 i 之后的数据是按序排的，故 num[j] + num[k] 只存在一组取值。
4、复杂度最优解代码示例
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
if (nums == null || nums.length < 3) {
return result;
}
Arrays.sort(nums);
for (int i = 0; i < nums.length - 2; i++) {
if (i > 0 && nums[i] == nums[i - 1]) {
continue;
}
int left = i + 1;
int right = nums.length - 1;
while (left < right) {
int sum = nums[i] + nums[left] + nums[right];
if (sum == 0) {
result.add(Arrays.asList(nums[i], nums[left], nums[right]));
while (left < right && nums[left] == nums[left + 1]) {
left++;
}
while (left < right && nums[right] == nums[right - 1]) {
right--;
}
left++;
right--;
} else if (sum < 0) {
left++;
} else {
right--;
}
}
}
return result;
}
5、抽象与扩展
将复杂的问题简单化，本题有3元变量，考虑降维成二元变量的可行性。
而就算是处理二元变量问题，暴力解决基本耗时是n*n。
优化点主要在找到二元变量相互的影响规则，然后用双指针来处理，此时复杂度是 n（找二元变量影响规则的原因：双指针在每次循环中只移动某个指针，而移动左指针或者右指针需要基于影响规则来确定）
二元变量相互的影响规则举例：
1、比如A、B两个变量，A+B=5，那么A增则B减，A减则B增。
2、贪心-盛最多水的容器
