用网站名查询网址培训学校

LeetCode 15. 三数之和

题目描述

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

注意：

• 答案中的三元组可以按任意顺序组织。
• 在 nums 中，除了同一个三元组中的元素可以重复外，不可以有重复的三元组。

示例 1：

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

示例 2：

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

示例 3：

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

Java 实现解法

方法一：排序 + 双指针

class Solution {public List<List<Integer>> threeSum(int[] nums) {Arrays.sort(nums); // 首先对数组进行排序List<List<Integer>> result = new ArrayList<>();for (int i = 0; i < nums.length - 2; i++) {if (nums[i] > 0) break; // 如果当前数字大于0，则后面的数字之和一定大于0if (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) {left++;} else if (sum > 0) {right--;} else {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--;}}}return result;}
}

解题思路

• 排序：首先对数组进行排序，这样可以通过一次遍历来找到所有可能的三元组，并且可以方便地跳过重复的解。
• 固定第一个数：遍历数组，对于每个元素 nums[i]，我们尝试找到两个其他元素，使得它们与 nums[i] 的和为 0。
• 双指针：对于每个 nums[i]，我们使用两个指针 left 和 right 分别指向 i + 1 和 nums.length - 1。这样，我们可以在这个范围内寻找和为 -nums[i] 的两个数。
• 跳过重复解：如果在数组中找到了相同的数字，跳过它们以避免重复的三元组。
• 更新指针：如果三数之和小于 0，则移动 left 指针；如果大于 0，则移动 right 指针；如果等于 0，则找到了一个解，并更新指针跳过重复的数字。

这种方法的时间复杂度是 O(n^2)，其中 n 是数组 nums 的长度。因为我们对数组进行了排序，然后进行了两层嵌套循环。空间复杂度是 O(1)，除了输入数组和输出列表外，我们没有使用额外的空间。

注：来源leetcode网站