学习笔记--算法（双指针）6

和为 s 的两个数字

链接：

. - 力扣（LeetCode）

---

题目

购物车内的商品价格按照升序记录于数组 price。请在购物车中找到两个商品的价格总和刚好是 target。若存在多种情况，返回任一结果即可。

示例 1：

输入：price = [3, 9, 12, 15], target = 18

输出：[3,15] 或者 [15,3]

示例 2：

输入：price = [8, 21, 27, 34, 52, 66], target = 61

输出：[27,34] 或者 [34,27]

提示：

1 <= price.length <= 10^5

1 <= price[i] <= 10^6

1 <= target <= 2*10^6

---

解法一（暴力枚举，超时）

算法思路

两层 for 循环列出所有两个数字的组合，判断是否等于⽬标值。

算法流程

两层 for 循环：

• 外层 for 循环依次枚举第⼀个数 a ；

• 内层 for 循环依次枚举第⼆个数 b ，让它与 a 匹配；

ps ：这⾥有个魔⻤细节：我们挑选第⼆个数的时候，可以不从第⼀个数开始选，因为 a 前⾯的数我们都已经在之前考虑过了；因此，我们可以从 a 往后的数开始列举。

• 然后将挑选的两个数相加，判断是否符合⽬标值。

代码省略。

---

解法二

图解

---

算法思路

注意到本题是升序的数组，因此可以⽤「对撞指针」优化时间复杂度。

---

算法流程（附带算法分析，为什么可以使⽤对撞指针）

a. 初始化 left ， right 分别指向数组的左右两端（这⾥不是我们理解的指针，⽽是数组的下标）

b. 当 left < right 的时候，⼀直循环：

i. 当 nums[left] + nums[right] == target 时，说明找到结果，记录结果，并且返回；

ii. 当 nums[left] + nums[right] < target 时：

• 对于 nums[left] ⽽⾔，此时 nums[right] 相当于是 nums[left] 能碰到的最⼤值（别忘了，这⾥是升序数组哈~）。如果此时不符合要求，说明在这个数组⾥⾯，没有别的数符合 nums[left] 的要求了（最⼤的数都满⾜不了你，你已经没救了）。因此，我们可以⼤胆舍去这个数，让 left++ ，去⽐较下⼀组数据；

• 那对于 nums[right] ⽽⾔，由于此时两数之和是⼩于⽬标值的， nums[right]还可以选择⽐ nums[left] ⼤的值继续努⼒达到⽬标值，因此 right 指针我们按兵不动；

iii. 当 nums[left] + nums[right] > target 时，同理我们可以舍去nums[right] （最⼩的数都满⾜不了你，你也没救了）。让 right-- ，继续⽐较下⼀组数据，⽽ left 指针不变。

---

代码

public int[] twoSum(int[] price, int target) {
    int left = 0;
    int right = price.length - 1;
    while(left < right){
        int sum = price[left] + price[right];
        if(sum < target){
            left++;
        }else if(sum > target){
            right--;
        }else{
            return new int[] {price[left],price[right]};
        }
    }
    return new int[]{0};
}