科普网站栏目建设方案,沧州市住房和城乡建设局网站,做直播的网站,seo属于什么职业部门一、问题描述
给定一个整数数组 nums#xff0c;判断是否存在三元组 [nums[i], nums[j], nums[k]]#xff0c;使得#xff1a; i ! j、i ! k 且 j ! k nums[i] nums[j] nums[k] 0
需要返回所有和为 0 的三元组#xff0c;且这些三元组不能重复。
输入输出 输入: 整…一、问题描述
给定一个整数数组 nums判断是否存在三元组 [nums[i], nums[j], nums[k]]使得 i ! j、i ! k 且 j ! k nums[i] nums[j] nums[k] 0
需要返回所有和为 0 的三元组且这些三元组不能重复。
输入输出 输入: 整数数组 nums 输出: 包含所有和为 0 的不重复三元组的列表
示例 输入: nums [-1,0,1,2,-1,-4]输出: [[-1,-1,2],[-1,0,1]] 解释存在两个不同的三元组它们的和均为 0。 输入: nums [0,1,1]输出: [] 解释不存在三元组的和为 0。 输入: nums [0,0,0]输出: [[0,0,0]] 解释唯一的三元组和为 0。
注意事项 输出的顺序和三元组内部的顺序不重要。 需确保返回的三元组不重复。
二、解题思路以及代码实现
方法 1: 排序 双指针法
解题思路 排序: 首先对输入数组进行排序。这是因为在有序数组中可以使用双指针法更有效地查找三元组。 遍历数组: 使用一个 for 循环遍历每个元素 nums[i]确保 nums[i] 是当前处理的元素避免重复。如果 nums[i] 大于 0由于数组是有序的后面的数都将更大所以可以结束循环。 双指针: 对于每个选定的 nums[i]设置两个指针left 指向 i1right 指向数组末尾。计算三数之和 current_sum nums[i] nums[left] nums[right]。 如果 current_sum 为 0保存该三元组并移动 left 和 right 指针跳过重复的元素。 如果 current_sum 小于 0移动 left 指针向右。 如果 current_sum 大于 0移动 right 指针向左。
时间复杂度 排序: O(n log n)排序不管是分治排序还是快排的时间复杂度都是 O(n log n)详细可以搜搜 双指针遍历: O(n²) 总时间复杂度: O(n log n n²) O(n²)
空间复杂度 O(k)其中 k 是输出中三元组的数量额外空间用于结果存储。
代码实现
def threeSum(self, nums: List[int]) - List[List[int]]:nums.sort() # 排序result []n len(nums)for i in range(n):if i 0 and nums[i] nums[i - 1]: # 跳过重复元素continueleft, right i 1, n - 1while left right:current_sum nums[i] nums[left] nums[right]if current_sum 0:result.append([nums[i], nums[left], nums[right]])# 跳过重复元素while left right and nums[left] nums[left 1]:left 1while left right and nums[right] nums[right - 1]:right - 1left 1right - 1elif current_sum 0:left 1else:right - 1 return result
方法 2: 哈希表法
解题思路 使用哈希表: 利用一个哈希集合来存储每个元素帮助快速查找。 遍历: 对于数组中的每个元素 nums[i]需要找到另外两个数 nums[j] 和 nums[k]使得 nums[i] nums[j] nums[k] 0。这可以转化为寻找 -nums[i] nums[j] nums[k]。 双重循环: 使用双重循环遍历数组中的所有可能的组合计算 target -nums[i]然后检查哈希表中是否存在可以与 nums[j] 组合成 target 的元素 nums[k]。 避免重复: 使用一个集合存储找到的三元组确保输出中不包含重复的三元组。
时间复杂度 外层循环: O(n)内层循环: O(n) 哈希表查找: O(1) 总时间复杂度: O(n²)
空间复杂度 O(n)用于存储哈希表和结果集合。
代码实现
def threeSum(nums):result set()n len(nums)for i in range(n):target -nums[i]seen set()for j in range(i 1, n):complement target - nums[j]if complement in seen:result.add((nums[i], nums[j], complement))seen.add(nums[j])return [list(triplet) for triplet in result]
