现在老公失业都不敢说话,烦死了,真的好无奈一点处理问题的能力都没有。
刚看到个贴子,说老公失业在家,动不动就躲着不说话,老婆一边烦一边又觉得无奈:人到中年了,一点处理问题的能力都没有。
在我看来,问题的根儿不只是“失业”,而是两个人都陷进了情绪里:他怕丢人就装缩头乌龟,她既要稳定收入,又要被照顾情绪,这就有点“既要又要还要”的味道了。
失业这事,说白了是家庭共同风险,不是一个人的耻辱。男人最起码要做到:把情况摊开讲清楚,列个计划,哪怕是先送外卖、干临时工,也是“我在动”;而不是闷头打游戏等机会。女人这边,也别一句“烦死了”挂在嘴上,多问一句“咱下一步怎么办”,比骂他有用。
算法题:三数之和
昨天晚上十一点多,我在公司楼下拿着奶茶吹风,本来想摸会儿鱼刷刷视频,结果手一滑点开了力扣,蹦出来一道老熟人题:三数之和。那一瞬间整个人清醒了,你们有没有这种,看到熟悉题目脑子比咖啡还提神的…
先说下这题在干嘛哈。大概意思就是:给你一个整数数组 nums,找出里面所有「不重复」的三元组 (a, b, c),让 a + b + c = 0。注意两个点,一个是不能少了情况,另一个是不能算重,比如 [-1, -1, 2] 只能算一次,顺序不管。
很多人一上来第一反应就跟我当年一样:暴力三层 for 啊,反正也能写:
defthree_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 notin res: # 去重,超级慢
res.append(triplet)
return res
这个写法有两个问题:一个是时间复杂度 O(n^3),数据一大直接超时;另一个是你看那个 triplet not in res,列表里找又是一层循环,等于雪上加霜。反正就是,能跑,但又慢又丑。
那我楼下抽完一根烟想了下,这题其实有一个特别常用的套路:排序 + 双指针。很多数组题都是这路子,背熟了能用一辈子那种。
思路我用大白话说一遍,你脑补一下画面:
先把数组排个序,举个例子:[-1, 0, 1, 2, -1, -4] 排完变成 [-4, -1, -1, 0, 1, 2] 然后我从左到右,一个个把 nums[i] 当「第一个数」固定住 剩下的事情就变成:在 i 右边那一段,找两个数,让它俩加起来等于 -nums[i] 在有序区间里找两数之和,你们知道吧,最顺手的就是双指针:左指针指向最左,右指针指向最右,和大了就右指针左移,和小了就左指针右移
听着有点绕,你看代码就一下子清楚了,我用 Python 写一份比较规整、能直接提交那种:
from typing import List
defthree_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 > 0and 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^2) 的复杂度,面试官一般都会点点头那种。你们留意几个细节哈,我顺嘴唠一唠:
第一,为什么一开始可以 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 的就那两组。
还有一个小点,顺手提一下: 你如果在刷题的时候,发现三数之和、四数之和、两数之和,这一串题其实都是一个模子刻出来的,只是维度不一样:两数之和可以哈希表;三数之和变成「枚举一个 + 两数之和双指针」;四数之和就是「枚举两个 + 两数之和」,套路通了之后,后面这些题基本都能秒。
行,差不多就这样,奶茶也喝完了,我得上楼把刚才那段代码塞回项目的 util 里去了,你要是正好也在刷题,可以先把这个版本手敲一遍,别直接复制,自己打出来一遍记得更牢。
-END-
我为大家打造了一份RPA教程,完全免费:songshuhezi.com/rpa.html
虎哥作为一名老码农,整理了全网最全《python高级架构师资料合集》,总量高达650GB