leecode-三数之和

我的github链接

思路

我的思路先顺序遍历一个变量,然后使用首尾双指针去遍历，根据结果去更新另外两个变量，如何和为零，将结果加入集合，但是这里要注意去重。

class Solution {

    public List<List<Integer>> threeSum(int[] nums) {

        // 排序，从小到大

        Arrays.sort(nums);

        List<List<Integer>> res = new ArrayList<>();

        //  如果数组为空直接返回

        if(nums == null || nums.length == 0){

            return res;

        }

         // 从0开始遍历

        for(int i = 0; i < nums.length - 2; i ++){

            // 如果说最小的元素都大于0，直接返回就好了

            if(nums[i] > 0){

                return res;

            }

            int j = i + 1, k = nums.length - 1;

            while(j < k){

                if((nums[i] + nums[j] + nums[k]) > 0){

                    k --;

                }else if((nums[i] + nums[j] + nums[k]) < 0){

                    j ++;

                }else{

                    List<Integer> list = new ArrayList<>();

                    list.add(nums[i]);

                    list.add(nums[j]);

                    list.add(nums[k]);

                    res.add(list);

                    j ++;

                    k --;

                }

            }

        }

        HashSet<List<Integer>> uniqueSet = new HashSet<>(res);

        List<List<Integer>> uniqueRes = new ArrayList<>(uniqueSet);

        return uniqueRes;

    }

}

优化去重之后的AC代码

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        // 排序，从小到大
        Arrays.sort(nums);
        List<List<Integer>> res = new ArrayList<>();
        //  如果数组为空直接返回
        if(nums == null || nums.length == 0){
            return res;
        }
         // 从0开始遍历
        for(int i = 0; i < nums.length - 2; i ++){
            // 如果说最小的元素都大于0，直接返回就好了
            if(nums[i] > 0){
                return res;
            }
            // 去重操作一
            if(i > 0 && nums[i] == nums[i - 1]){
                continue;
            }
            int j = i + 1, k = nums.length - 1;
            while(j < k){
                if((nums[i] + nums[j] + nums[k]) > 0){
                    k --;
                }else if((nums[i] + nums[j] + nums[k]) < 0){
                    j ++;
                }else{
                    List<Integer> list = new ArrayList<>();
                    list.add(nums[i]);
                    list.add(nums[j]);
                    list.add(nums[k]);
                    res.add(list);
                    // 去重操作二
                    while(j < k && nums[j] == nums[j + 1]){
                        j ++;
                    }
                    while(j < k && nums[k] == nums[k - 1]){
                        k --;
                    }
                    j ++;
                    k --;
                }
            }
        }
       
        return res;
    }
}

题解

你提供的代码说明你已经掌握了解决这道题目的正确方向：“排序 + 双指针”。这非常了不起！现在遇到的问题，只是通往成功之路上的一点小坎坷，我们一起来把它彻底弄明白。

题目：LeetCode 15. 三数之和 (3Sum)

题目理解

给你一个整数数组 nums，你需要找出其中所有不重复的、和为 0 的三元组 [nums[i], nums[j], nums[k]]。

关键点：

1. 和为 0：a + b + c = 0

2. 不重复：返回的 List 中不能包含重复的三元组。例如，对于输入 [-1, 0, 1, 2, -1, -4]，排序后是 [-4, -1, -1, 0, 1, 2]，其中 [-1, 0, 1] 这个三元组只需要返回一次，即使数组中有两个 -1 都可以组成这个结果。

样例

• 输入: nums = [-1, 0, 1, 2, -1, -4]

• 输出: [[-1, -1, 2], [-1, 0, 1]]

我的思路分析与困惑解答

首先，我要给你点个赞！你的整体思路非常正确，代码框架也搭建得很好。你遇到的困惑——“为什么还是通过不了”，根源在于 重复解的处理方式。

你的代码是在找出所有可能的三元组（包括重复的）之后，最后利用 HashSet 来进行去重。

Java

// 你的去重方式
HashSet<List<Integer>> uniqueSet = new HashSet<>(res);
List<List<Integer>> uniqueRes = new ArrayList<>(uniqueSet);
return uniqueRes;

这个方法有两个主要问题：

1. 效率问题：当输入数组中包含大量重复元素时（例如 [0, 0, 0, 0, 0, ...]），你的循环会产生巨量的重复结果，并将它们全部加入 res 列表。这个过程本身就非常耗时，最后再进行去重，很容易导致“超出时间限制 (Time Limit Exceeded)”。

2. 思维误区：在算法设计中，我们追求的是在过程中就避免产生不必要的结果，而不是“先污染，后治理”。一个优秀的算法应该像一个精准的狙击手，只命中目标，而不是像散弹枪一样打出一大片再来筛选。

正确的做法是：在双指针移动的过程中，通过判断和跳过重复的元素，来根本性地杜绝重复解的产生。

正确的解题思路：排序 + 双指针 + 剪枝去重

让我们一步一步来构建这个“精准”的算法。

Step 1: 排序数组

这是整个算法的基石。为什么一定要排序？

• 有序性：方便我们使用双指针从两端向中间移动。如果左指针 L 的数小了，我们就向右移动 L 找一个更大的数；如果右指针 R 的数大了，我们就向左移动 R 找一个更小的数。这种单向移动的策略，在无序数组中是无法实现的。

• 去重：相同的元素会聚集在一起，这为我们“跳过”重复元素提供了极大的便利。

Step 2: 固定一个数，将“三数之和”降维为“两数之和”

我们使用一个 for 循环来遍历整个数组，每次循环固定一个数 nums[i]。

Java

for (int i = 0; i < nums.length - 2; i++) {
    // ...
}

现在，我们的目标就变成了在数组 i 之后的部分，寻找两个数 nums[L] 和 nums[R]，使得 nums[i] + nums[L] + nums[R] == 0。这等价于寻找 nums[L] + nums[R] == -nums[i]。

你看，我们成功地将一个复杂的三数问题，转化成了一个我们更熟悉的“两数之和”问题！

Step 3: 双指针法解决“两数之和”

我们在 i 之后的部分设置左右两个指针：

• 左指针 L 指向 i + 1

• 右指针 R 指向数组末尾 nums.length - 1

然后在一个 while (L < R) 循环中，计算三个数的和 sum = nums[i] + nums[L] + nums[R]：

• 如果 sum < 0，说明总和太小了，需要增大。因为 nums[i] 固定，nums[R] 已经是右侧最大的了，所以我们只能移动左指针 L++ 来让 sum 变大。

• 如果 sum > 0，说明总和太大了，需要减小。同理，我们只能移动右指针 R-- 来让 sum 变小。

• 如果 sum == 0，恭喜！我们找到了一个解。将 [nums[i], nums[L], nums[R]] 加入结果集。

Step 4: 算法的精髓 —— 剪枝与去重

这是解决你困惑最关键的一步，我们要在循环中加入逻辑来“剪掉”不必要的分支和“去掉”重复的结果。

1. 对 nums[i] 的剪枝与去重

   • 剪枝：如果我们固定的 nums[i] 已经大于 0，由于数组是排好序的，后面的 nums[L] 和 nums[R] 也必然大于 0，三数之和不可能等于 0。所以可以直接 break 循环。

   • 去重：当 i > 0 时，如果 nums[i] 和它前一个数 nums[i-1] 相等，那么以 nums[i] 为首找到的三元组，必然和以 nums[i-1] 为首找到的三元组重复。所以，我们直接 continue 跳过本次循环。

2. 对 nums[L] 和 nums[R] 的去重

   • 当我们找到一个 sum == 0 的解后，我们需要继续移动 L 和 R 来寻找下一个可能的解。

   • 此时，必须防止 nums[L] 和 nums[R] 的重复。例如，对于 [-2, 0, 0, 2, 2]，当 i=0 (num=-2), L=1 (num=0), R=4 (num=2) 时，我们找到了 [-2, 0, 2]。

   • 如果不做处理，直接 L++，R--，那么 L 会指向第二个 0，R 会指向第一个 2，又会找到一个 [-2, 0, 2]，这就重复了。

   • 所以，在找到一个解之后，我们要用 while 循环跳过所有与当前 nums[L] 和 nums[R] 相等的元素。

数据结构选择

• List<List<Integer>>: 这是题目要求返回的类型。我们使用 ArrayList 来实现，因为它支持动态扩容，适合存储数量不确定的结果。

• 在解题过程中，我们仅使用了指针（整型变量）和输入数组本身，没有引入额外复杂的数据结构，这也是这个解法空间效率高的原因。

完整 Java 代码实现

Java

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

class Solution {

    /**
     * 解决三数之和问题的核心方法
     * @param nums 输入的整数数组
     * @return 包含所有不重复三元组的列表
     */
    public List<List<Integer>> threeSum(int[] nums) {
        // 1. 初始化结果列表
        List<List<Integer>> result = new ArrayList<>();

        // 2. 边界条件判断：如果数组为空或长度小于3，不可能构成三元组
        if (nums == null || nums.length < 3) {
            return result;
        }

        // 3. 对数组进行排序，这是双指针算法的前提
        Arrays.sort(nums);

        // 4. 主循环：固定第一个数 nums[i]
        //    i 的范围到倒数第三个数即可，因为后面需要留给 L 和 R 两个指针
        for (int i = 0; i < nums.length - 2; i++) {

            // 5. 优化与剪枝（一）：
            //    如果固定的数 nums[i] 大于 0，因为数组已排序，
            //    后面的数都大于0，三数之和不可能为0，可以直接结束循环。
            if (nums[i] > 0) {
                break;
            }

            // 6. 关键去重（一）：对固定的数 nums[i] 进行去重
            //    如果当前的 nums[i] 与前一个数 nums[i-1] 相同，
            //    则说明这种情况已经被处理过了，跳过以避免重复解。
            //    i > 0 是为了防止 i=0 时 i-1 越界。
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }

            // 7. 定义双指针 L 和 R
            int left = i + 1; // 左指针，从 i 的下一个位置开始
            int right = nums.length - 1; // 右指针，从数组末尾开始

            // 8. 双指针移动，寻找和为 -nums[i] 的两个数
            while (left < right) {
                int sum = nums[i] + nums[left] + nums[right];

                if (sum == 0) {
                    // 8.1. 找到了一个解
                    result.add(Arrays.asList(nums[i], nums[left], nums[right]));

                    // 8.2. 关键去重（二）：移动左右指针，并跳过所有重复的元素
                    //    防止出现例如 [-2, 0, 0, 2, 2] 中，[-2, 0, 2] 被重复添加
                    while (left < right && nums[left] == nums[left + 1]) {
                        left++;
                    }
                    while (left < right && nums[right] == nums[right - 1]) {
                        right--;
                    }

                    // 8.3. 移动指针到下一个不同的元素
                    left++;
                    right--;

                } else if (sum < 0) {
                    // 8.4. 如果和小于0，说明需要更大的数，左指针右移
                    left++;
                } else { // sum > 0
                    // 8.5. 如果和大于0，说明需要更小的数，右指针左移
                    right--;
                }
            }
        }
        
        // 9. 返回最终结果
        return result;
    }
}

复杂度分析

• 时间复杂度: O(N2)

  • Arrays.sort(nums) 的时间复杂度是 O(NlogN)。

  • 外层 for 循环遍历 i，复杂度为 O(N)。

  • 内层 while 循环中，left 和 right 指针总共最多走 N 步。所以内层循环的复杂度是 O(N)。

  • 总的时间复杂度是 O(NlogN+NtimesN)=O(N2)。

• 空间复杂度: O(logN) 或 O(N)

  • 这取决于排序算法使用的额外空间。Java 的 Arrays.sort 对于基本数据类型使用的是快速排序的变种，其空间复杂度平均为 O(logN)，最坏情况下为 O(N)。

  • 我们没有使用额外的哈希表等数据结构。返回结果 result 列表的空间不计入算法的额外空间复杂度。

举一反三：同类思路题目

掌握了“排序 + 双指针”这个强大的思想范式后，你可以去挑战下面这些题目，它们都是这个思路的延伸或变种：

• [[LeetCode 1. 两数之和]] (可以用哈希表，也可以用排序+双指针)

• [[LeetCode 16. 最接近的三数之和]] (思路几乎一样，只是判断条件从 == 0 变成了求 min(abs(sum - target)) )

• [[LeetCode 18. 四数之和]] (思路升级：固定两个数，然后用双指针解决“两数之和”)

• [[LeetCode 11. 盛最多水的容器]] (经典的对撞双指针问题)

补充

好的，作为一名精通Java的高级程序员，很高兴能为您总结这个问题。对一个 List<List<Integer>> 集合，要对其中的元素 List<Integer> 进行去重，核心在于 List 接口的实现类（如 ArrayList）已经正确地重写了 equals() 和 hashCode() 方法。这两个方法是基于列表中的元素内容和顺序来判断两个列表是否相等的。

因此，我们可以利用所有依赖这两个方法来进行元素唯一性判断的Java特性。

下面我为您总结几种常用且高效的方法，并分析其优缺点和适用场景。

方法一：使用 HashSet (最常用、最高效)

这是最经典也是最直接的方法。Set 集合本身就保证了元素的唯一性，将 List 直接转为 HashSet 即可自动完成去重。

原理：

HashSet 在添加元素时，会先计算元素的 hashCode() 值来确定存储位置，然后通过 equals() 方法判断该位置上是否已存在相同元素。由于 ArrayList 等 List 实现类已经正确实现了这两个方法，所以可以直接利用 HashSet 的特性进行去重。

代码示例：

Java

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

public class DeduplicateExample {
    public static void main(String[] args) {
        List<List<Integer>> originalList = new ArrayList<>();
        originalList.add(Arrays.asList(1, 2, 3));
        originalList.add(Arrays.asList(4, 5));
        originalList.add(Arrays.asList(1, 2, 3)); // 重复元素
        originalList.add(Arrays.asList(6));
        originalList.add(Arrays.asList(4, 5));   // 重复元素

        System.out.println("原始列表: " + originalList);

        // 1. 将原列表中的所有元素添加到 HashSet 中，自动去重
        HashSet<List<Integer>> uniqueSet = new HashSet<>(originalList);

        // 2. 将 Set 转换回 List
        List<List<Integer>> deduplicatedList = new ArrayList<>(uniqueSet);

        System.out.println("去重后列表: " + deduplicatedList);
    }
}

优点：

• 代码简单：一行代码即可完成核心去重逻辑。

• 性能优秀：HashSet 的添加和查找操作的平均时间复杂度为 O(1)，整体去重的时间复杂度接近 O(n)（其中n是外层列表的元素数量）。

缺点：

• 不保证顺序：HashSet 是无序的，去重后的列表元素的顺序与原始列表的顺序可能不同。如果需要保持顺序，请看下面的方法。

方法二：使用 Java 8 Stream API (最推荐、最简洁)

对于使用 Java 8 及以上版本的开发者来说，Stream API 提供了非常优雅和简洁的解决方案。

原理：

Stream.distinct() 方法会返回一个由不同元素（根据 Object.equals(Object) 方法）组成的流。它会维持一个内部状态来记录所有已经出现过的元素，从而实现去重。

代码示例：

Java

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

public class DeduplicateExample {
    public static void main(String[] args) {
        List<List<Integer>> originalList = new ArrayList<>();
        originalList.add(Arrays.asList(1, 2, 3));
        originalList.add(Arrays.asList(4, 5));
        originalList.add(Arrays.asList(1, 2, 3)); // 重复元素
        originalList.add(Arrays.asList(6));
        originalList.add(Arrays.asList(4, 5));   // 重复元素

        System.out.println("原始列表: " + originalList);

        // 使用 Stream 的 distinct() 方法去重
        List<List<Integer>> deduplicatedList = originalList.stream()
                .distinct()
                .collect(Collectors.toList());

        System.out.println("去重后列表: " + deduplicatedList);
    }
}

优点：

• 代码简洁优雅：链式调用，可读性强，是现代Java编程的推荐方式。

• 保持相对顺序：distinct() 方法会保留每个重复元素第一次出现的顺序，对于有序流（List 创建的流就是有序的），去重后的结果是稳定的。

• 功能强大：可以和其他流操作（如 filter, map 等）无缝结合，进行更复杂的数据处理。

缺点：

• 相比直接使用 HashSet，在某些极端性能场景下可能会有微小的性能开销，但绝大多数情况下可以忽略不计。

方法三：使用 LinkedHashSet (需要保持插入顺序)

如果你既需要去重，又希望保持元素插入时的顺序，LinkedHashSet 是最佳选择。

原理：

LinkedHashSet 继承自 HashSet，同样具有元素唯一的特性。同时，它内部使用一个链表来维护元素的插入顺序。

代码示例：

Java

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

public class DeduplicateExample {
    public static void main(String[] args) {
        List<List<Integer>> originalList = new ArrayList<>();
        originalList.add(Arrays.asList(1, 2, 3));
        originalList.add(Arrays.asList(4, 5));
        originalList.add(Arrays.asList(1, 2, 3)); // 重复元素
        originalList.add(Arrays.asList(6));
        originalList.add(Arrays.asList(4, 5));   // 重复元素

        System.out.println("原始列表: " + originalList);

        // 1. 使用 LinkedHashSet 去重并保持插入顺序
        LinkedHashSet<List<Integer>> uniqueSet = new LinkedHashSet<>(originalList);

        // 2. 将 Set 转换回 List
        List<List<Integer>> deduplicatedList = new ArrayList<>(uniqueSet);

        System.out.println("去重后列表 (保持顺序): " + deduplicatedList);
    }
}

优点：

• 元素唯一：和 HashSet 一样。

• 保持插入顺序：这是它相比 HashSet 的最大优势。

• 性能良好：同样具有接近 O(1) 的添加和查找性能。

缺点：

• 相比 HashSet，需要额外维护链表，会占用更多的内存。

方法四：手动迭代去重 (传统方式)

在没有高级集合类或Stream API的时代，或者在某些需要更复杂去重逻辑的场景下，可以手动迭代。

原理：

创建一个新列表用于存放结果，同时用一个 Set 来记录已经添加过的元素。遍历原始列表，只有当元素未在 Set 中出现时，才将其添加到新列表和 Set 中。

代码示例：

Java

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

public class DeduplicateExample {
    public static void main(String[] args) {
        List<List<Integer>> originalList = new ArrayList<>();
        originalList.add(Arrays.asList(1, 2, 3));
        originalList.add(Arrays.asList(4, 5));
        originalList.add(Arrays.asList(1, 2, 3));
        originalList.add(Arrays.asList(6));
        originalList.add(Arrays.asList(4, 5));

        System.out.println("原始列表: " + originalList);

        List<List<Integer>> deduplicatedList = new ArrayList<>();
        Set<List<Integer>> seen = new HashSet<>();

        for (List<Integer> innerList : originalList) {
            if (seen.add(innerList)) { // Set.add() 如果元素不存在则添加成功并返回 true
                deduplicatedList.add(innerList);
            }
        }

        System.out.println("去重后列表 (手动迭代): " + deduplicatedList);
    }
}

优点：

• 逻辑清晰：易于理解底层的去重过程。

• 保持顺序：结果列表的顺序与原始列表中元素的首次出现顺序一致。

• 灵活性高：可以在 if 判断中加入更复杂的业务逻辑。

缺点：

• 代码冗余：相比前几种方法，代码量更多，不够简洁。

总结与对比

最终建议：

• 在现代Java（8及以上版本）开发中，首选使用 Stream.distinct()，它在简洁性、可读性和功能性上达到了完美的平衡。

• 如果项目未使用Java 8，或者对性能有极致要求且不关心顺序，HashSet 是最简单高效的选择。

• 如果必须保持插入顺序，那么 LinkedHashSet 是最直接的答案。