三数之和

三数之和（3Sum）要求在给定的整数数组中，找出所有满足三个数相加等于目标值的三元组，且结果不能包含重复的三元组。

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

public class ThreeSum {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        // 首先对数组进行排序
        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;
    }
}

解释每一步：

1. 首先对数组进行排序，这样可以方便后续使用双指针法进行遍历。

2. 遍历数组，将三数之和问题转化为两数之和问题。在遍历的过程中，每次固定一个数 nums[i]，并在其后面的范围内使用双指针法找到两数之和等于目标值的组合。

3. 使用双指针法，左指针 left 指向当前元素的下一个位置，右指针 right 指向数组的最后一个元素。

4. 如果三数之和等于目标值，则将该三元组添加到结果列表中，并继续向内收缩指针以避免重复解。

5. 如果和小于目标值，增大左指针；如果和大于目标值，减小右指针。

6. 重复以上步骤直到遍历完成。

这种解法的时间复杂度为 O(n^2)，其中 n 是数组的长度。因为我们首先对数组进行排序，排序的时间复杂度为 O(nlogn)，然后使用双指针法在最坏情况下的时间复杂度为 O(n^2)。空间复杂度为 O(1)，因为只使用了常数级别的额外空间。