6.LeetCode 剑指Offer 57 和为s的两个数，暴力到双指针法！

目录

题目解析

算法原理（暴力 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^5

• 1 <= 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提交版（变量名用price）

class 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的两个数