99元一月做网站北京国贸网站建设

题目链接

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

问题分析

暴⼒解法，会超时
（两层 for 循环列出所有两个数字的组合，判断是否等于⽬标值。）

算法流程：
初始化 left ， right 分别指向数组的左右两端（这⾥不是我们理解的指针，⽽是数组的下标）
当 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 指针不变（还是可以去匹配⽐ nums[right] 更⼩的数的）。

与上一题思路类似

代码解决

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};}
}

执行用时