15. 三数之和

Bin大约 2 分钟

15. 三数之和

题目：三数之和

描述：

给定一个整数数组 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 中存在两个不同的三元组：
[-1, -1, 2] 和 [-1, 0, 1]。

示例 2:

输入: nums = []
输出: []

示例 3:

输入: nums = [0]
输出: []

解题思路：

为了找到所有满足条件的三元组，并确保结果不重复，可以使用 排序 + 双指针 的方法。

算法步骤：

对数组进行排序，便于去重和使用双指针。
遍历数组，固定一个数 nums[i]，然后在 i 后面的子数组中使用双指针寻找和为 -nums[i] 的两个数。
- 左指针指向 i+1，右指针指向数组末尾。
- 如果三数之和大于 0，右指针左移；如果小于 0，左指针右移。
跳过重复的数，避免产生重复的三元组。

代码实现：

import java.util.Scanner;
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // 读取数组长度
        int n = scanner.nextInt();
        int[] nums = new int[n];

        // 读取数组元素
        for (int i = 0; i < n; i++) {
            nums[i] = scanner.nextInt();
        }

        Solution solution = new Solution();
        List<List<Integer>> result = solution.threeSum(nums);

        // 输出结果
        System.out.print("[");
        for (int i = 0; i < result.size(); i++) {
            System.out.print("[");
            List<Integer> triplet = result.get(i);
            for (int j = 0; j < triplet.size(); j++) {
                System.out.print(triplet.get(j));
                if (j < triplet.size() - 1) {
                    System.out.print(", ");
                }
            }
            System.out.print("]");
            if (i < result.size() - 1) {
                System.out.print(", ");
            }
        }
        System.out.println("]");

        scanner.close();
    }
}

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        Arrays.sort(nums); // 1. 排序

        for (int i = 0; i < nums.length - 2; i++) {
            // 跳过重复的数字
            if (i > 0 && nums[i] == nums[i - 1]) continue;

            int left = i + 1, 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++; // 如果和小于0，移动左指针
                } else {
                    right--; // 如果和大于0，移动右指针
                }
            }
        }

        return result;
    }
}

时间复杂度分析：

排序：O(n log n)，其中 n 是数组的长度。
双指针遍历：O(n^2)，外层循环一次，内层双指针扫描一次。

因此，时间复杂度为 O(n^2)。

空间复杂度分析：

使用的额外空间主要是存储结果，因此空间复杂度为 O(k)，其中 k 是结果中三元组的数量。

总结：

通过排序和双指针方法，我们可以有效解决三数之和问题，同时避免了结果的重复性。代码易于理解且性能较优，适合在中等规模数据下运行。