网站建设哪个公司服务好,可以自己做效果图的网站,dede仿网站目录,网站模板 金融题目
LCR 179. 查找总价格为目标值的两个商品 购物车内的商品价格按照升序记录于数组 price。请在购物车中找到两个商品的价格总和刚好是 target。若存在多种情况#xff0c;返回任一结果即可。 示例 1#xff1a; 输入#xff1a;price [3, 9, 12, 15], target 18 输出返回任一结果即可。 示例 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 解法1哈希表
哈希表解法就类似于1. 两数之和这题的解法也就是一边遍历一边将遍历到的数可能的解存起来然后看看后面会不会遍历到这个数 class Solution {
public:vectorint twoSum(vectorint price, int target) {setint st;for(auto ele:price){if(st.find(ele)!st.end()) return vectorint{ele, target-ele};else st.insert(target-ele);}return vectorint{-1, -1};}
};解法2滑动指针数学
哈希表解法相对于暴力遍历两轮当然复杂度不会太高但是这道题还有一个条件是升序数组并没有用到实际上如果利用头尾两个指针计算其和当过大时就让尾指针向左移动缩小和当和过小时就让头指针向右移动增大和这样便免去了哈希表的哈希过程的时间那么这样可能错过该有的解吗其实不会设想和大于目标值也就是最小的元素最大的元素大于目标值此时尾指针递减其实就是直接排除了尾部元素因为此时已经知道了最大元素与最小元素的和都会超过目标值所以最大元素必不可能是目标值的组成元素之一所以可以直接排除 class Solution {
public:vectorint twoSum(vectorint price, int target) {int i0, jprice.size()-1, sum;while(i!j){sumprice[i]price[j];if(sumtarget) return vectorint{price[i], price[j]};sumtarget ? i : --j; }return vectorint{-1, -1};}
};
