class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        // n：记录数组的长度
        int n = nums.length;
        // 1. 先对数组进行升序排序，这是后续能够使用双指针和去重的前提
        Arrays.sort(nums);
        // ans：用于存放最终所有不重复的符合条件的三元组集合
        List<List<Integer>> ans = new ArrayList<List<Integer>>();
        
        // i：外层循环指针，遍历整个数组，作为三元组的第一个固定数
        for (int i = 0; i < nums.length; i++) {
            // 剪枝优化：因为数组已经排序，如果当前固定的 nums[i] 已经大于 0
            // 那么它后面的数肯定也都大于 0，三个正数相加不可能等于 0，直接结束循环
            if (nums[i] > 0) {
                break;
            }
            // 第一层去重：如果当前固定的 nums[i] 与前一个数相同（如 -3, -3, 1, 2）
            // 那么该数作为首元素的情况已经处理过，直接跳过避免结果重复
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            
            // left：左指针，指向当前 i 之后的第一个元素
            int left = i + 1;
            // right：右指针，指向数组的最后一个元素
            int right = n - 1;
            
            // 当左指针在右指针左边时，继续查找
            while (left < right) {
                // num：计算当前三个指针指向的元素之和
                int num = nums[i] + nums[left] + nums[right];
                
                if (num == 0) {
                    // 如果三数之和正好为 0，将这三个元素构成 List 添加到结果集中
                    ans.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 (num < 0) {
                    // 如果三数之和小于 0，说明左侧的数太小，左指针向右移动寻找更大的数
                    left++;
                } else {
                    // 如果三数之和大于 0，说明右侧的数太大，右指针向左移动寻找更小的数
                    right--;
                }
            }
        }
        // 循环结束后返回包含所有不重复三元组的结果集
        return ans;
    }
}