刚在网上看到一个帖子，说的是老公失业在家，动不动就躲着不吭声。老婆这边呢，一边觉得心烦，一边又感到无奈，觉得人到中年了，怎么一点处理问题的能力都没有。
要我说，这事儿的关键可能不只是“失业”本身，而是两个人都陷进了情绪里。他怕丢脸，就选择当“缩头乌龟”；她既要家里的收入稳定，又希望对方能主动处理好情绪——这多少有点“既要又要还要”的味道了。
其实，失业说白了是家庭需要共同面对的风险，不是某个人的“耻辱”。作为当事人，最起码得做到把情况摊开说清楚，列个计划。哪怕是先去送送外卖、干点临时工，也是在传递“我在行动”的信号，总比闷头打游戏干等着强。另一方呢，也别把“烦死了”总挂在嘴边，试着问一句“咱们接下来该怎么办”，可能比单纯抱怨更有用。
算法题：三数之和
昨天晚上十一点多，我在公司楼下拿着奶茶吹风，本来想摸鱼刷会儿视频，结果手一滑点开了力扣，一道老熟人题目蹦了出来：「三数之和」。那一瞬间整个人都清醒了，不知道你们有没有过这种体验——看到熟悉的题目，脑子比灌了咖啡还提神。
先说说这题要干嘛。简单讲，就是给你一个整数数组 nums，要你找出里面所有 不重复 的三元组 (a, b, c)，并且满足 a + b + c = 0。这里有两个关键点：一是情况不能漏，二是结果不能重复。比如 [-1, -1, 2] 这个组合只能算一次，顺序调换不算新组合。
很多人的第一反应（包括当年的我）就是：三层 for 循环暴力破解，反正能写出来就行：
def three_sum_bruteforce(nums):
n = len(nums)
res = []
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 res: # 去重，超级慢
res.append(triplet)
return res
这个写法问题很明显：首先，时间复杂度是 O(n³)，数据量稍大肯定超时；其次，你看那个 triplet not in res，在列表里查找又是一层循环，简直是雪上加霜。总结就是：能跑，但既慢又丑。
我在楼下抽了根烟想了想，这题其实有一个非常经典的套路：排序 + 双指针。很多数组相关的题目都吃这一套，属于学会了能受益很久的那种。
让我用大白话把思路捋一遍：
- 先排序：例如数组
[-1, 0, 1, 2, -1, -4]，排完序变成 [-4, -1, -1, 0, 1, 2]。
- 固定第一个数：从左到右，依次把
nums[i] 当作三元组里的第一个数固定下来。
- 转化问题：那么剩下的任务就变成了——在
i 右边的子数组里，找到两个数，让它们的和等于 -nums[i]。
- 双指针解决：在一个有序区间里找“两数之和”，最顺手的就是双指针法。左指针指向剩余区间最左端，右指针指向最右端。如果三数之和大于0，说明太大了，右指针左移；如果小于0，说明太小了，左指针右移。
光说可能有点绕，直接看代码就一目了然了。下面是一份比较规整、可以直接提交的Python实现：
from typing import List
def three_sum(nums: List[int]) -> List[List[int]]:
nums.sort() # 1. 先排序
n = len(nums)
res = []
for i in range(n):
# 小优化：第一个数已经大于 0，那后面全是非负，肯定不可能凑出 0 了
if nums[i] > 0:
break
# 跳过相同的第一个数，避免结果重复
if i > 0 and nums[i] == nums[i - 1]:
continue
left = i + 1
right = n - 1
while left < right:
s = nums[i] + nums[left] + nums[right]
if s == 0:
res.append([nums[i], nums[left], nums[right]])
# 这两个 while 是关键：跳过相同的第二、第三个数
left_val = nums[left]
right_val = nums[right]
while left < right and nums[left] == left_val:
left += 1
while left < right and nums[right] == right_val:
right -= 1
elif s < 0:
# 和太小了，说明需要更大一点的数，左指针右移
left += 1
else:
# 和太大了，需要更小一点的数，右指针左移
right -= 1
return res
这个版本就优雅多了，整体时间复杂度是 O(n²)，属于面试官看了会点头的那种。有几个细节值得特别唠叨一下：
第一，为什么可以 if nums[i] > 0: break？
因为数组已经排好序了，nums[i] 是当前能选到的最小的数。如果它都已经大于0，那它后面的所有数也都 ≥ 它，三个正数相加怎么可能等于0呢？直接结束循环，能省下很多无用的计算。
第二，“去重”到底在去什么？
这题最烦人的地方其实不是算法思路，而是各种重复。重复可能发生在三个地方：
- 第一个数重复：
if i > 0 and nums[i] == nums[i - 1]: continue
- 第二个数重复：找到一个有效解后，
while left < right and nums[left] == left_val: left += 1
- 第三个数重复：同理，对
right 指针也进行相同的跳过操作
如果不这么处理，想象一下数组里有多个 -1，那么 i 相同、left 相同、right 相同的组合会被多次加入结果列表，输出一堆重复的三元组，这在面试中可是大忌。
第三，别忘了边界情况。
我昨晚在楼下想的时候，风一吹差点把这茬忘了：
- 数组长度小于3，直接返回空列表。
- 数组元素全为正数或全为负数（如
[1, 2, 3, 4]），排序后第一个数就大于0，前面的优化会直接 break，返回正确结果 []。
- 像
[0, 0, 0, 0] 这种情况，按我们的写法也只会留下一个 [0, 0, 0]，不会重复也不会遗漏。
可以写个简单的测试用例跑一下，心里更踏实：
if __name__ == "__main__":
nums = [-1, 0, 1, 2, -1, -4]
print(three_sum(nums))
# 可能的输出（顺序不重要）：
# [[-1, -1, 2], [-1, 0, 1]]
看一下就知道逻辑是对的：排序后是 [-4, -1, -1, 0, 1, 2]，能凑成0的就是那两组。
最后一个小提示：
如果你在刷题时发现，两数之和、三数之和、四数之和这一系列题目，其实都是同一个模子刻出来的，只是维度不同。两数之和可以用哈希表；三数之和就变成了“固定一个数 + 两数之和（双指针版）”；四数之和则是“固定两个数 + 两数之和”。套路打通之后，后面这些题基本都能迎刃而解。
好了，奶茶喝完了，算法也聊完了。我得把这思考过程记下来，分享到开发者广场和大家交流。如果你正好也在刷题，建议把上面的代码亲手敲一遍，别直接复制，自己敲一遍记忆更深刻。
发表于 昨天 18:35
|
查看: 1|
回复: 0
