网站分为哪几个部分,外包 网站开发公司,WordPress加入百度地图,梵克雅宝官网中文官网这里写自定义目录标题 题目链接问题分析代码解决执行用时 题目链接
购物车内的商品价格按照升序记录于数组 price。请在购物车中找到两个商品的价格总和刚好是 target。若存在多种情况#xff0c;返回任一结果即可。
问题分析
暴⼒解法#xff0c;会超时 #xff08;两层… 这里写自定义目录标题 题目链接问题分析代码解决执行用时 题目链接
购物车内的商品价格按照升序记录于数组 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};}
}执行用时
