★ 算法OJ题 ★ 力扣 LCR179 - 和为 s 的两个数字

Ciallo～(∠・ω< )⌒☆ ~ 今天，小诗歌剧将和大家一起做一道双指针算法题--和为 s 的两个数字~

目录

一  题目

二  算法解析

三  编写算法

---

一  题目

LCR 179. 查找总价格为目标值的两个商品 - 力扣（LeetCode）

二  算法解析

解法⼀：暴力解法 O(N ^ 2)

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

class Solution {
public:vector<int> twoSum(vector<int>& nums, int target) {int n = nums.size();for (int i = 0; i < n; i++) // 第⼀层循环从前往后列举第⼀个数{ for (int j = i + 1; j < n; j++) // 第⼆层循环从 i 位置之后列举第⼆个数{ if (nums[i] + nums[j] == target) // 两个数的和等于⽬标值，说明我们已经找到结果了return { nums[i], nums[j] };}}return { -1, -1 };}
};

解法⼆：利用单调性，使用双指针 - 对撞指针解决问题

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

三  编写算法

class Solution {
public:vector<int> twoSum(vector<int>& price, int target) {int left = 0, right = price.size() - 1;while(left < right){int sum =  price[left] + price[right];if(sum == target)return {price[left], price[right]};if(sum < target)left++;if(sum > target)right--;}return { -1, -1 };}
};