目录题目解析算法原理暴力 vs 双指针解法一暴力枚举O(n²)—— 适合小数据但别用在LeetCode上解法二双指针法O(n)—— 本题最优解编写代码Java版LeetCode提交版变量名用price总结 心得大二生的碎碎念OJ链接LeetCode 剑指Offer 57. 和为s的两个数作为一名大二计算机学生最近在刷LeetCode热题今天刚啃完剑指Offer 57. 和为s的两个数从暴力枚举到双指针优化今天把我的理解笔记全部分享出来题目解析先看题目输入一个递增排序的数组和一个数字s在数组中查找两个数使得它们的和正好是s。如果有多对数字的和等于s则输出任意一对即可。示例1输入nums [2,7,11,15], target 9输出[2,7]或者[7,2]示例2输入nums [10,26,30,31,47,60], target 40输出[10,30]或者[30,10]限制1 nums.length 10^51 nums[i] 10^6算法原理暴力 vs 双指针刚开始我第一反应是暴力枚举两层for循环枚举所有两个数的组合看和是否等于target。但这样时间复杂度是O(n²)对于10^5的数据量肯定超时后来看到“递增排序”这个关键词瞬间想到双指针法因为数组有序我们可以用两个指针从两端往中间夹根据当前和与target的大小关系来移动指针时间复杂度直接降到O(n)解法一暴力枚举O(n²)—— 适合小数据但别用在LeetCode上代码思路for (int i 0; i n; i) { for (int j i 1; j n; j) { if (nums[i] nums[j] target) return ...; } }解法二双指针法O(n)—— 本题最优解核心思想利用数组单调递增的性质用左指针left指向开头右指针right指向末尾计算sum nums[left] nums[right]如果sum target→ 说明右边太大右指针左移right--如果sum target→ 说明左边太小左指针右移left如果sum target→ 找到答案返回编写代码Java版LeetCode提交版变量名用priceclass Solution { public int[] twoSum(int[] price, int target) { int left 0, right price.length - 1; while (left right) { int sum price[left] price[right]; if (sum target) { right--; } else if (sum target) { left; } else { return new int[]{price[left], price[right]}; } } // 照顾编译器 return new int[]{0}; } }总结 心得大二生的碎碎念做完这道题我最大的收获是一定要关注题目中的“隐藏条件”比如这里的“递增排序”就是双指针法的灵魂。如果没有这个条件双指针可能就不适用了比如乱序数组还得用哈希表。另外暴力枚举虽然简单但在数据量大时绝对会超时所以算法优化真的很重要从O(n²)到O(n)虽然只是换了个思路但效率提升了一个量级这就是算法的魅力吧~OJ链接LeetCode 剑指Offer 57. 和为s的两个数