package DataStructure.array;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 15. 三数之和 https://leetcode.cn/problems/3sum/
 * 题目简述:找出一个数组中所有三个不同位置和为0的不重复的三元组
 */
public class ThreeSum {

 public static void main(String[] args) {
 new ThreeSum().threeSum(new int[]{-2,0,1,1,2});
 }

 /**
 * 思路:三指针解法。先将数组升序排序,然后指针i从左向右每遍历一个元素,指针j,k从[i+1, len-1]两端开始向中间扫描,寻找所有包含i的三数之和为0的三元组。j,k移动过程中:
 * 1. 若三数之和为0,则添加结果,然后将j,k向中间移动一步继续寻找解,并略过重复元素,避免加入重复的三元组
 * 2. 若三数之和小于0,则说明j要向右移动,以增大当前和
 * 3. 若三数之和大于0,则说明k要向左移动,以减小当前和
 */
 public List<List<Integer>> threeSum(int[] nums) {
 List<List<Integer>> result = new ArrayList<>();
 //先排好序
 Arrays.sort(nums);
 //然后从左向右每遍历一个元素i,指针j,k从[i+1, len-1]两端开始向中间扫描,寻找所有包含i的三数之和为0的三元组
 for (int i = 0;i < nums.length;i++) {
 //若nums[i] > 0,则后面的元素都已经大于0了,三数之和不可能为0,直接退出循环
 if (nums[i] > 0) break;
 //重复的i元素得出的三元组肯定是一样的,直接过滤掉
 if(i > 0 && nums[i] == nums[i-1]) continue;
 int j = i + 1;
 int k = nums.length - 1;
 while (j < k) {
 int sum = nums[i] + nums[j] + nums[k];
 if (sum == 0) {
 //1.若三数之和为0,则添加结果,然后将j,k向中间移动继续寻找解,并略过重复元素,避免加入重复的三元组
 result.add(Arrays.asList(nums[i], nums[j], nums[k]));
 j++;
 while (j < k && nums[j] == nums[j-1]) {
 j++;
 }
 k--;
 while (j < k && nums[k] == nums[k+1]) {
 k--;
 }
 } else if (sum < 0) {
 //2.若三数之和小于0,则说明j要向右移动,以增大三数之和
 j++;
 } else {
 //3.若三数之和大于0,则说明k要向左移动,以减小三数之和
 k--;
 }
 }
 }
 return result;
 }
}