HomeArchivesCategoriesLabelMomentsPhotosLinkAbout

LeetCode 15. 三数之和

学习
44
0
0
2022-04-01
LeetCode 15. 三数之和

LeetCode 15. 三数之和

问题描述

给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。注意：答案中不可以包含重复的三元组。

示例 1：

输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]

输入：nums = [-1,0,1,2,-1,-4] 输出：[[-1,-1,2],[-1,0,1]]

示例 2：

输入：nums = []
输出：[]

示例 3：

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

提示：

  • 0 <= nums.length <= 3000

  • -10^5 <= nums[i] <= 10^5

思路

方法一：暴力穷举法

这个方法的思想是使用三层 for 循环，穷举所有可能的情况，将符合题目条件的结果保存到 res 中。由于该方法的时间复杂度较高，所以在 LeetCode 上提交时会显示超出时间限制的提示。此外，要注意在查找的过程中去掉重复的三元组。

方法二：排序 & 双指针法

这个方法使用排序和双指针的思想来解决问题。具体解题思路如下：

  1. 对数组 nums 进行排序。

  2. 使用一个 for 循环来穷举第一个元素 nums[i]。

  3. 对于每一个 nums[i]，改写 LeetCode 1. 两数之和 这题中的解法来找到和为 target - nums[i] 的二元组。

  4. 如果找到和为 target - nums[i] 的二元组，那么该二元组再加上 nums[i] 就是和为 target 的三元组。

  5. 使用一个 while 循环来跳过重复元素。

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums); // 对数组进行排序
        List<List<Integer>> res = new ArrayList<>();
        for (int i = 0; i < nums.length - 2; i++) {
            if (nums[i] > 0) {
                break; // 如果 nums[i] 为正数，后面不存在符合条件的三元组
            }
            if (nums[i] + nums[i + 1] + nums[i + 2] > 0) {
                break; // 如果当前相邻的三个元素之和大于 0，后面不存在符合条件的三元组
            }
            if (nums[i] + nums[nums.length - 1] + nums[nums.length - 2] < 0) {
                continue; // 如果当前相邻的三个元素之和小于 0，直接进行下一趟循环
            }
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue; // 防止包含重复的三元组
            }
            for (int j = i + 1; j < nums.length - 1; j++) {
                if (nums[i] + nums[j] + nums[j + 1] > 0) {
                    break;
                }
                if (nums[i] + nums[j] + nums[nums.length - 1] < 0) {
                    continue;
                }
                if (j > i + 1 && nums[j] == nums[j - 1]) {
                    continue;
                }
                for (int k = j + 1; k < nums.length; k++) {
                    if (nums[i] + nums[j] + nums[k] > 0) {
                        break;
                    }
                    if (nums[i] + nums[j] + nums[nums.length - 1] < 0) {
                        continue;
                    }
                    if (k > j + 1 && nums[k] == nums[k - 1]) {
                        continue;
                    }
                    if (nums[i] + nums[j] + nums[k] == 0) {
                        res.add(new ArrayList<>(Arrays.asList(nums[i], nums[j], nums[k])));
                    }
                }
            }
        }
        return res;
    }
}

总结

本题的解法涉及了排序和双指针的应用，通过穷举第一个元素，然后使用双指针在有序数组中查找剩下的两个元素，来找到和为 0 的三元组。同时，要注意去重操作，以保证结果中不包含重复的三元组。希望这个解题思路对你有所帮助。

#LeetCode 9