👤作者介绍:10年大厂数据\经营分析经验,现任大厂数据部门负责人。
会一些的技术:数据分析、算法、SQL、大数据相关、python
作者专栏每日更新:
LeetCode解锁1000题: 打怪升级之旅LeetCode解锁1000题: 打怪升级之旅https://blog.csdn.net/cciehl/category_12625714.html
python数据分析可视化:企业实战案例https://blog.csdn.net/cciehl/category_12615648.html
备注说明:方便大家阅读,统一使用python,带必要注释,公众号 数据分析螺丝钉 一起打怪升级
在算法和数据结构的学习中,"三数之和"问题是一个非常经典的问题,它不仅考验着程序员的基础算法能力,还涉及到如何有效地利用数据结构来解决实际问题。接下来,我们将通过一个由浅入深的方式,详细解析这个问题,并给出相应的案例和代码实现。
问题描述
在"三数之和"问题中,给定一个包含 n 个整数的数组 nums
,判断 nums
中是否存在三个元素 a,b,c,使得 a + b + c = 0?找出所有满足条件且不重复的三元组。
简单解法 — 暴力法(不推荐)
一种最直观的方法是使用三重循环遍历所有可能的三元组组合,检查它们的和是否为 0。虽然这种方法简单直观,但其时间复杂度为 O(n^3),在数据量较大时会导致严重的性能问题。
代码实现
def three_sum_brute_force(nums):
n = len(nums)
result = []
for i in range(n):
for j in range(i+1, n):
for k in range(j+1, n):
if nums[i] + nums[j] + nums[k] == 0:
triplet = sorted([nums[i], nums[j], nums[k]])
if triplet not in result:
result.append(triplet)
return result
高效解法 — 双指针法
为了优化算法,我们可以采用双指针法。首先对数组进行排序,然后使用一个固定指针遍历数组,对于每个固定指针的位置,使用两个指针(一个在固定指针之后,一个在数组末尾),通过移动这两个指针来搜索和为0的三元组。
解题步骤
- 排序:对数组进行排序。
- 遍历:固定一个数 nums[i],然后使用左右指针指向 nums[i] 后面的两端,数字分别为 nums[L] 和 nums[R],计算三个数的和 sum 判断是否满足条件。
- 去重:跳过重复的数字。
代码实现
def three_sum(nums):
nums.sort()
n, result = len(nums), []
for i in range(n):
if i > 0 and nums[i] == nums[i-1]:
continue
L, R = i+1, n-1
while L < R:
total = nums[i] + nums[L] + nums[R]
if total < 0:
L += 1
elif total > 0:
R -= 1
else:
result.append([nums[i], nums[L], nums[R]])
while L < R and nums[L] == nums[L+1]:
L += 1
while L < R and nums[R] == nums[R-1]:
R -= 1
L += 1
R -= 1
return result
案例分析
假设输入数组为 nums = [-1, 0, 1, 2, -1, -4]
。
- 排序后的数组为
[-4, -1, -1, 0, 1, 2]
。 - 固定第一个数为
-4
,在-1
到2
的范围内寻找两数之和为4
的组合,不存在,移动固定数。 - 固定第二个数为第一个
-1
,找到了两数之和为1
的组合,即[-1, 0, 1]
。 - 继续遍历,找到第二个组合为
[-1, -1, 2]
。
双指针法图解
给定一个数组nums = [-4, -1, -1, 0, 1, 2]
,目标是找出所有唯一的三元组,它们的和为0。
1. 排序
首先,对数组进行排序。
排序后的数组: [-4, -1, -1, 0, 1, 2]
2. 遍历和双指针搜索
对数组进行遍历,每次遍历中,固定一个元素,然后用两个指针在固定元素之后的数组部分进行搜索,一个指针从左向右移动(左指针),另一个从右向左移动(右指针)。
第一轮遍历
- 固定元素:
-4
(索引0) - 左指针: 在
-1
(索引1) - 右指针: 在
2
(索引5)
数组: [-4, -1, -1, 0, 1, 2]
固定元素: -4 (索引0)
左指针: ↑ (索引1)
右指针: ↑ (索引5)
检查和调整
- 第一次和为
-4 + (-1) + 2 = -3 < 0
,左指针向右移动。 - 左指针移动到第二个
-1
处,和为-4 + (-1) + 2 = -3 < 0
,左指针继续向右移动。 - 左指针移动到
0
处,和为-4 + 0 + 2 = -2 < 0
,左指针继续向右移动,直到左指针与右指针相遇,这轮遍历结束。
在这轮遍历中,没有找到和为0的三元组。
第二轮遍历
- 固定元素变为:
-1
(索引1) - 左指针: 在
-1
(索引2) - 右指针: 在
2
(索引5)
数组: [-4, -1, -1, 0, 1, 2]
固定元素: -1 (索引1)
左指针: ↑ (索引2)
右指针: ↑ (索引5)
遍历的过程重复上述步骤,对每个固定元素,移动左右指针,并根据三数之和是大于还是小于0来调整指针的位置。
关键点
- 当和小于0时,只移动左指针向右。
- 当和大于0时,只移动右指针向左。
- 当找到和为0的三元组时,记录下来,并同时移动左指针和右指针,寻找新的可能组合。
3. 去重
为了避免记录重复的三元组,每次在移动指针时,需要跳过重复的值。
结论
通过以上的解析和示例代码,我们可以看出,相比于暴力法,双指针法大大提高了"三数之和"问题的求解效率。