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网站
