欢迎阅读一.题目LCR 179. 查找总价格为目标值的两个商品 - 力扣LeetCode​ 欢迎来到「查找总价格为目标值的两个商品」题解之旅本文将带你从“在有序数组中寻找两数之和为目标值”这一经典问题出发深入理解双指针对撞指针的简洁高效并掌握如何利用有序性快速定位答案。在开始之前建议你先了解题目背景这是 LCR 179 题原 LeetCode 167 两数之和 II 的变体给定一个已按升序排列的数组price和目标值target要求找到两个数的和恰好等于target返回任意一组结果即可。本质上这是一道有序数组中的两数之和问题可用双指针在 O(n)O(n) 时间内解决比哈希表更省空间。明确学习目标掌握对撞双指针策略——左指针指向最小元素右指针指向最大元素计算两数之和若小于目标则左指针右移增大和若大于目标则右指针左移减小和若等于则找到答案。理解为什么在有序数组中这种“按需调整指针”的策略能保证不漏解并熟练处理边界条件如保证有唯一解无需额外判空。准备好环境建议在本地 IDE 或 LeetCode 在线编辑器中打开代码边看边运行亲手验证示例如price [3, 9, 12, 15], target 18输出[3, 15]。本文将从问题转化、双指针策略设计对撞指针、指针移动逻辑到代码实现层层递进。即使你对双指针还不熟悉我们也会从“一头一尾往中间靠”这一直觉出发让你轻松抓住核心思想——有序数组的优势在于可以用大小控制指针移动方向快速逼近目标值。现在让我们一起在价格列表中快速锁定那对恰好匹配的商品吧 二.做题思路一、问题分析前置分析给定一个升序排列的数组price要求找到两个数使它们的和等于target。数组长度可达 1e5需O(n) 时间解决。核心观察利用数组有序的特性可以使用双指针从两端向中间逼近通过比较当前和与目标值动态调整指针从而在 O(n) 内找到答案。二、算法策略双指针初始化左指针left 0最小值右指针right n-1最大值。循环条件left right计算当前和sum price[left] price[right]。若sum target则左指针右移left以增大和若sum target则右指针左移right--以减小和若sum target则找到答案直接返回{price[left], price[right]}。题目保证有唯一解循环内必返回。示例执行过程price [3, 9, 12, 15],target 18步骤leftrightsum比较操作初始0331518 target返回[3, 15]直接命中无需移动。再举一个需要移动的例子price [8, 21, 27, 34, 52, 66],target 61步骤leftrightsum比较操作10 (8)5 (66)7461right--20 (8)4 (52)6061left31 (21)4 (52)7361right--41 (21)3 (34)5561left52 (27)3 (34)6161返回[27, 34]最终得到正确结果。三、正确性说明简单版本因为数组升序当前左指针指向最小值右指针指向最大值。若两数之和小于目标则任何数与左指针配对都不可能达到目标因为右指针已最大所以必须将左指针右移增大最小值反之若和大于目标则任何数与右指针配对都不可能达到目标因为左指针已最小必须将右指针左移。此过程不会遗漏任何可能的组合每次移动都排除了一个方向的无效候选直到找到答案。该策略能保证在有解情况下一定找到正确结果。四、实现细节边界防护初始化left 0right n-1。在循环内先计算sum再比较然后移动指针最后更新sum或每次重新计算。循环条件left right避免下标越界。题目保证有解因此无需处理无解情况。时间复杂度 O(n)空间复杂度 O(1)除返回结果外。五、返回值目标映射返回一个包含两个数的vectorint即满足price[i] price[j] target的任意一对价格。三.代码#include iostream #include vector using namespace std; class Solution { public: vectorint twoSum(vectorint price, int target) { // 算法思路双指针法 // 由于数组已按升序排列可以使用左右指针分别指向数组两端。 // 计算两数之和若小于目标值则左指针右移增大和若大于目标值则右指针左移减小和 // 若等于目标值则找到答案返回这两个数。 // 因为题目保证有唯一解所以一定会在循环内找到并返回。 vectorint v; // 存储结果的两个数 int n price.size(); int left 0; // 左指针指向最小元素 int right n - 1; // 右指针指向最大元素 int sum price[left] price[right]; // 初始两数之和 // 当左指针小于右指针时持续查找 while (left right) { // 如果当前和小于目标则需要增大和因此左指针右移 if (sum target) { left; } // 如果当前和大于目标则需要减小和因此右指针左移 else if (sum target) { right--; } // 如果当前和等于目标找到答案存入 vector 并退出循环 else { v.push_back(price[left]); v.push_back(price[right]); break; } // 指针移动后更新当前两数之和供下一次循环判断使用 sum price[left] price[right]; } // 返回包含两个数的 vector return v; } }; int main() { // 测试用例升序数组目标和为 9 vectorint price {2, 7, 11, 15}; int target 9; Solution sol; vectorint result sol.twoSum(price, target); cout result[0] result[1] endl; return 0; }四、易错点分析4.1 指针移动后未及时更新sum导致使用过期数据cppif (sum target) { left; } else if (sum target) { right--; } // 若此处缺少 sum 更新则下一次循环仍用旧 sum sum price[left] price[right];易错原因指针移动后必须立即重新计算sum否则下一次循环判断时使用的仍是移动前的和。初学者容易在left或right--后忘记更新sum或者在else分支找到答案中break前未处理更新虽然break后不影响但若代码重构时可能遗漏。必须确保每次指针变化后都重新计算sum且更新语句放在循环末尾或分支内部保证下一次循环开始时sum是有效的。五、流程图 闭幕 恭喜你完成了「查找总价格为目标值的两个商品」问题的学习为了巩固知识并进一步拓展建议你动手实践在 LeetCode 上提交代码尝试不同的测试用例。深入思考本题数组已按升序排列因此可以使用双指针从两端向中间逼近。请问为什么选择从两端开始而不是从同一侧开始其背后的单调性依据是什么如果数组未排序双指针法是否还能直接使用此时应如何调整解法给出思路和复杂度题目要求返回任一结果即可。当前算法在找到第一对满足条件的组合后就返回请问返回的是最靠左的组合还是最靠右的组合为什么数组元素可能重复例如[2,2,3,3]target5双指针移动逻辑是否会跳过某些有效组合请举例验证。算法中每次移动指针后更新sum如果left和right指针移动后sum的计算在循环末尾是否可能存在漏更新的情况延伸挑战如果要求返回所有满足条件的数对而不是仅返回任意一对你的代码应做哪些改动时间复杂度会变成多少如果数组包含负数例如[-5, 0, 3, 8]target3当前的双指针逻辑是否仍然有效为什么如果你觉得本文对你有所帮助欢迎点赞 / 收藏关注作者获取更多题解留言交流你的疑问或优化思路深入思考答案从两端开始是因为数组有序两端的和一端最小、一端最大移动较小的一端可以单调增大和移动较大的一端可以单调减小和从而高效逼近目标这是双指针在有序数组中利用单调性的核心。若未排序双指针失效需改用哈希表记录已遍历元素时间复杂度 O(n)空间 O(n)或先排序再双指针但排序会改变原数组且需要 O(n log n)。当前算法返回的是最左边的一对即left尽可能小、right尽可能大因为指针从两端向中间移动首次找到时left是最小索引right是最大索引但题目不要求具体哪一组所以任意。重复元素不影响例如[2,2,3,3]target5left0(2)right3(3)和为5立即返回(2,3)不会跳过其他组合因为找到任一即可。sum在循环末尾更新确保每次指针移动后重新计算不会漏更新初始sum在循环前计算循环内先判断后移动再更新逻辑正确。延伸挑战答案挑战1要返回所有数对可改为双指针遍历完整数组每当找到一对就记录然后同时移动left和right--直到指针相交。时间复杂度仍为 O(n)但需要处理重复值去重若要求唯一组合需跳过相同元素。挑战2负数情况下依然有效因为数组有序双指针的单调性依然成立负数只会影响和的大小但移动指针的规则不变和小了左移和大了右移算法完全适用。祝你在算法之路上越走越稳早日攻克每一道难题下次见 ✨