15. 三数之和#

public List<List<Integer>> threeSum(int[] nums) {
    // 使用 Set 自动去重：相同三元组（元素顺序一致）只会保留一份
    Set<List<Integer>> result = new HashSet<>();

    // i 选择三元组中的第一个元素
    for (int i = 0; i < nums.length; i++) {
        // j 选择三元组中的第二个元素（下标需大于 i）
        for (int j = i + 1; j < nums.length; j++) {
            // k 选择三元组中的第三个元素（下标需大于 j）
            for (int k = j + 1; k < nums.length; k++) {
                // 判断当前三个数之和是否为 0
                if (nums[i] + nums[j] + nums[k] == 0) {
                    // 对三个数排序，以避免重复
                    // triplet 保存当前命中的三元组
                    List<Integer> triplet = Arrays.asList(nums[i], nums[j], nums[k]);
                    // 排序后 [-1,0,1] 与 [0,-1,1] 会变成同一个顺序，便于 Set 去重
                    Collections.sort(triplet);
                    // 加入结果集合；若已存在相同三元组，Set 会自动忽略
                    result.add(triplet);
                }
            }
        }
    }

    // 按题目要求返回 List 结构
    return new ArrayList<>(result);
}

排序后：[-4,-1,-1,0,1,2]

固定-4：
目标找和为4的两个数
left=1,right=5: -1+2=1<4，left++
left=2,right=5: -1+2=1<4，left++
left=3,right=5: 0+2=2<4，left++
left=4,right=5: 1+2=3<4，结束

固定第一个-1：
目标找和为1的两个数
left=2,right=5: -1+2=1，找到[-1,-1,2]！
right--继续找...

固定第二个-1：（跳过，避免重复）

固定0：
目标找和为0的两个数
left=4,right=5: 1+2=3>0，right--
left=4,right=4：指针相遇，结束

public List<List<Integer>> threeSum(int[] nums) {
    // result 用于保存所有不重复的三元组答案
    List<List<Integer>> result = new ArrayList<>();
    // 先排序，这对去重和使用双指针非常关键
    Arrays.sort(nums);

    // i 固定三元组中的第一个数，最多到 nums.length - 3
    for (int i = 0; i < nums.length - 2; i++) {
        // 如果第一个数就大于0，后面肯定没有解
        if (nums[i] > 0) break;

        // 跳过重复的第一个数
        if (i > 0 && nums[i] == nums[i-1]) continue;

        // 使用双指针寻找另外两个数
        // left 从 i 右侧开始向右移动
        int left = i + 1;
        // right 从数组末尾开始向左移动
        int right = nums.length - 1;

        // 当 left 与 right 未相遇时，区间内仍有候选组合
        while (left < right) {
            // sum 表示当前三个数的和
            int sum = nums[i] + nums[left] + nums[right];

            if (sum == 0) {
                // 命中一个解，按升序（排序后天然满足）加入结果
                result.add(Arrays.asList(nums[i], nums[left], nums[right]));

                // 跳过重复的数
                // 跳过与当前 left 值相同的后续元素，避免产生重复三元组
                while (left < right && nums[left] == nums[left+1]) left++;
                // 跳过与当前 right 值相同的前序元素，避免产生重复三元组
                while (left < right && nums[right] == nums[right-1]) right--;

                // 继续寻找其他解
                // 两侧同时收缩，尝试新的数值组合
                left++;
                right--;
            } else if (sum < 0) {
                // 和偏小：需要更大的值，移动 left 使和增大
                left++;
            } else {
                // 和偏大：需要更小的值，移动 right 使和减小
                right--;
            }
        }
    }

    // 返回所有不重复三元组
    return result;
}