不是所有“三数之和”都要等于 0 ——聊聊 3Sum Smaller 背后的算法思维

不是所有“三数之和”都要等于 0 ——聊聊 3Sum Smaller 背后的算法思维

大家好，我是Echo_Wish。
如果你刷过 LeetCode，3Sum这个题你大概率不陌生，甚至可能已经被它“教育”过好几次 😅。

但今天我们聊的不是那个经典的：

三个数相加等于 0

而是它一个更有意思、也更贴近工程思维的变种：

较小的三数之和（3Sum Smaller）

说白了就是一句话：

给你一个数组 nums 和一个目标值 target，问有多少个三元组 (i, j, k)，满足
nums[i] + nums[j] + nums[k] < target。

注意关键词：
不是找组合，而是“数数量”。

一、这道题为什么值得你认真想一想？

先说结论：
3Sum Smaller 是一道“看似简单，实则非常考察算法直觉”的题。

因为它逼着你从三个层面思考问题：

1. 暴力解