怎么把网站地图上传,东平可信的网站建设,公司网站关键词优化,有哪些网站做汽车周边服务LeetCode 热题100 | 15. 三数之和
大家好#xff0c;今天我们来解决一道经典的算法题——三数之和。这道题在 LeetCode 上被标记为中等难度#xff0c;要求我们从一个整数数组中找到所有不重复的三元组#xff0c;使得三元组的和为 0。下面我将详细讲解解题思路#xff0c…LeetCode 热题100 | 15. 三数之和
大家好今天我们来解决一道经典的算法题——三数之和。这道题在 LeetCode 上被标记为中等难度要求我们从一个整数数组中找到所有不重复的三元组使得三元组的和为 0。下面我将详细讲解解题思路并附上 Python 代码实现。 题目描述
给定一个整数数组 nums判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i ! j、i ! k 且 j ! k同时还满足 nums[i] nums[j] nums[k] 0。请你返回所有和为 0 且不重复的三元组。
示例
输入nums [-1,0,1,2,-1,-4]
输出[[-1,-1,2],[-1,0,1]]解题思路
这道题的核心是找到所有满足条件的三元组同时避免重复。我们可以通过排序数组和双指针法来高效地解决这个问题。
核心思想 排序数组 将数组排序方便后续使用双指针法。 遍历数组 固定一个数 nums[i]然后在剩下的数组中使用双指针法寻找两个数 nums[left] 和 nums[right]使得 nums[i] nums[left] nums[right] 0。 双指针法 初始化 left i 1right len(nums) - 1。如果 nums[i] nums[left] nums[right] 0则 left 右移。如果 nums[i] nums[left] nums[right] 0则 right 左移。如果 nums[i] nums[left] nums[right] 0则找到一个三元组记录下来并跳过重复的元素。 去重 在遍历过程中跳过重复的 nums[i]、nums[left] 和 nums[right]避免重复的三元组。 代码实现
def threeSum(nums)::type nums: List[int]:rtype: List[List[int]]nums.sort() # 排序数组result [] # 存储结果for i in range(len(nums) - 2): # 遍历数组固定 nums[i]if i 0 and nums[i] nums[i - 1]: # 跳过重复的 nums[i]continueleft, right i 1, len(nums) - 1 # 初始化双指针while left right:total nums[i] nums[left] nums[right] # 计算三数之和if total 0:left 1 # 和小于 0左指针右移elif total 0:right - 1 # 和大于 0右指针左移else:result.append([nums[i], nums[left], nums[right]]) # 找到一个三元组# 跳过重复的 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 - 1return result代码解析 排序数组 将数组排序方便后续使用双指针法。 遍历数组 固定一个数 nums[i]然后在剩下的数组中使用双指针法寻找两个数 nums[left] 和 nums[right]。 双指针法 初始化 left i 1right len(nums) - 1。根据三数之和的大小移动 left 或 right 指针。 去重 在遍历过程中跳过重复的 nums[i]、nums[left] 和 nums[right]避免重复的三元组。 复杂度分析
时间复杂度O(n²)其中 n 是数组的长度。排序的时间复杂度为 O(n log n)双指针法的时间复杂度为 O(n²)。空间复杂度O(1)只使用了常数个额外空间。 示例运行
示例 1
# 输入nums [-1,0,1,2,-1,-4]
nums [-1, 0, 1, 2, -1, -4]
print(threeSum(nums)) # 输出: [[-1, -1, 2], [-1, 0, 1]]示例 2
# 输入nums [0,1,1]
nums [0, 1, 1]
print(threeSum(nums)) # 输出: []示例 3
# 输入nums [0,0,0]
nums [0, 0, 0]
print(threeSum(nums)) # 输出: [[0, 0, 0]]总结
通过排序数组和双指针法我们可以高效地找到所有满足条件的三元组并避免重复。这种方法的时间复杂度为 O(n²)能够处理较大的输入规模。希望这篇题解对你有帮助如果还有其他问题欢迎继续提问
关注我获取更多算法题解和编程技巧
