算法题 法算day6 lief 2025-11-21 2025-11-21 三数之和 问题描述 给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。注意： 答案中不可以包含重复的三元组。
示例 1： 注意， 输出的顺序和三元组的顺序并不重要。
示例 2：
示例 3：
提示：
python版（排序+双指针） 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 def threeSum(nums): """ 寻找所有和为0的不重复三元组 使用排序 + 双指针的方法 """ # 先对数组进行排序，方便后续去重和双指针操作 nums.sort() n = len(nums) result = [] # 存储结果列表 # 遍历数组，固定第一个数 for i in range(n - 2): # 只需要遍历到倒数第三个数 # 如果当前数大于0，由于数组已排序，后面的数都大于0，不可能和为0，直接退出 if nums[i] > 0: break # 跳过重复的第一个数，避免重复三元组 if i > 0 and nums[i] == nums[i - 1]: continue # 设置双指针：left从i+1开始，right从末尾开始 left = i + 1 right = n - 1 # 双指针向中间移动 while left < right: # 计算当前三个数的和 total = nums[i] + nums[left] + nums[right] if total < 0: # 和太小，左指针右移（因为数组已排序，右移会增大和） left += 1 elif total > 0: # 和太大，右指针左移（因为数组已排序，左移会减小和） right -= 1 else: # 找到和为0的三元组，添加到结果中 result.append([nums[i], nums[left], nums[right]]) # 跳过重复的left值 while left < right and nums[left] == nums[left + 1]: left += 1 # 跳过重复的right值 while left < right and nums[right] == nums[right - 1]: right -= 1 # 移动双指针继续寻找 left += 1 right -= 1 return result # 测试代码 if __name__ == "__main__": # 示例1 nums1 = [-1, 0, 1, 2, -1, -4] print(threeSum(nums1)) # 输出: [[-1, -1, 2], [-1, 0, 1]] # 示例2 nums2 = [0, 1, 1] print(threeSum(nums2)) # 输出: [] # 示例3 nums3 = [0, 0, 0] print(threeSum(nums3)) # 输出: [[0, 0, 0]]
✅ 说明：
时间复杂度：排序操作：nums.sort() 使用 Timsort 算法，时间复杂度为 O(n log n)
空间复杂度：O(n)（主要由排序算法所需空间决定）
示例1详解
[]
java版 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 import java.util.*; public class ThreeSum { public List<List<Integer>> threeSum(int[] nums) { // 创建结果列表，用于存储所有满足条件的三元组 List<List<Integer>> result = new ArrayList<>(); // 如果数组为空或长度小于3，直接返回空结果 if (nums == null || nums.length < 3) { return result; } // 对数组进行排序，这是解决三数之和问题的关键步骤 Arrays.sort(nums); // 遍历数组，固定第一个数 for (int i = 0; i < nums.length - 2; i++) { // 如果当前数大于0，由于数组已排序，后面的数都大于0，三数之和不可能为0，直接结束循环 if (nums[i] > 0) { break; } // 跳过重复的元素，避免出现重复的三元组 if (i > 0 && nums[i] == nums[i - 1]) { continue; } // 使用双指针法，在i之后的子数组中寻找另外两个数 int left = i + 1; // 左指针指向i的下一个位置 int right = nums.length - 1; // 右指针指向数组末尾 // 当左右指针没有相遇时，继续寻找 while (left < right) { // 计算当前三个数的和 int sum = nums[i] + nums[left] + nums[right]; if (sum == 0) { // 如果和为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) { // 如果和小于0，说明需要更大的数，左指针右移 left++; } else { // 如果和大于0，说明需要更小的数，右指针左移 right--; } } } return result; } // 测试代码 public static void main(String[] args) { ThreeSum solution = new ThreeSum(); // 示例1 int[] nums1 = {-1, 0, 1, 2, -1, -4}; System.out.println(solution.threeSum(nums1)); // 输出: [[-1, -1, 2], [-1, 0, 1]] // 示例2 int[] nums2 = {0, 1, 1}; System.out.println(solution.threeSum(nums2)); // 输出: [] // 示例3 int[] nums3 = {0, 0, 0}; System.out.println(solution.threeSum(nums3)); // 输出: [[0, 0, 0]] } }
