P3000. 双十一

解题思路

注意，本题和 最接近的三数之和 几乎完全一致。唯一的区别在于，本题仅需要考虑 小于 R 的情况，不需要考虑大于 R 的情况。显然本题是 更简单 的。

假设与排序

假设所选的三个商品价格分别为 first、second 和 third，我们可以人为地假设这三者存在大小关系：first ≤ second ≤ third。

为了令所选的三个数之和尽可能地接近 R，我们可以先对价格数组进行 升序排序，然后从小到大考虑每一个元素作为 first，而 second 和 third 的选择则考虑使用 相向双指针 来完成。

相向双指针算法

second 和 third 的选择的相向双指针算法，类似于 经典题型的 167. 两数之和 II。

对于选择了第 i 个元素为 first 的情况，我们初始化 left = i + 1 和 right = n - 1 为两个相向双指针，并且规定 second = lst[left] 和 third = lst[right]，根据 first + second + third 和最大额度 R 之间的大小关系，来修改 left 和 right。若：

• first + second + third ≤ R：说明 first + second + third 是一个符合题目要求的选择，将三者和与 ans 进行比较并更新 ans，同时令 left 右移，才有可能找到更大的三者和。
• first + second + third > R：说明 first + second + third 不是一个符合题目要求的选择，此时无需更新 ans，同时令 right 左移，三者和才能变小。

暴力解法

当然，本题的数据量很小，n 的最大值只有 100。即使不使用双指针算法，而是直接使用 三重循环枚举 的暴力解法，时间复杂度 O(n³) = O(10⁶) 也是可以通过全部用例的。