剑指42-和为S的两个数
2023-02-18 16:41:12 时间
滑窗、双指针
题目描述
输入一个递增排序的数组和一个数字S,在数组中查找两个数,使得他们的和正好是S,如果有多对数字的和等于S,输出两个数的乘积最小的。
输出描述
对应每个测试案例,输出两个数,小的先输出。
解法1
滑窗
定义两个指针,一个在头,一个在尾
进入循环,左指针不超过右指针
当前和小于sum时,左指针右移,当前和大于sum时,右指针左移,如果西昂等,继续判断乘积
class Solution {
public:
vector<int> FindNumbersWithSum(vector<int> array,int sum) {
vector<int> res;
int l=0, r=array.size()-1;
int mul=INT_MAX;
while(l<r)
{
if(array[l]+array[r]<sum)
{
l++;
}
else if(array[l]+array[r]>sum)
{
r--;
}
else
{
if(array[l]*array[r]<mul) {
mul=array[l]*array[r];
res={array[l], array[r]};
}
l++;
r--;
}
}
return res;
}
};
解法2
双指针:
其实这个和解法1都是双指针,不过不同的是,这里两个指针起点相邻
而且这里复杂度为o(n^2)
class Solution {
public:
vector<int> FindNumbersWithSum(vector<int> array,int sum) {
vector<int> res;
int l=0, r=array.size()-1;
int mul=INT_MAX;
for(int l=0;l<array.size();l++)
{
for(int r=l+1;r<array.size();r++)
{
if(array[l]+array[r]<sum)
{
continue;
}
else if(array[l]+array[r]>sum)
{
break;
}
else
{
if(array[l]*array[r]<mul)
{
mul=array[l]*array[r];
res={array[l], array[r]};
}
}
}
}
return res;
}
};
相关文章
- laravel 中字段格式处理
- 开发中遇到的越权问题
- ES 简单操作指令
- shell 脚本提示权限不够的几种解决方式
- laravel 之 Unit 单元测试
- yii 配置文件根据模式分类
- ssh通过证书登陆服务器
- mac 安装Yapi
- YII2 控制器中不能使用大写的问题
- 接口测试第11讲:接口性能测试
- gin 数据绑定
- gin 框架将路由文件单独处理
- gin 读取配置文件
- zsh 好用的配置
- 接口测试第12讲:接口安全性测试
- 【实用的开源项目】使用服务器部署memos,一款拥有社交功能的、好看的自托管备忘录
- 接口测试第13讲:与Jenkins集成
- 将pem证书转换成p12格式证书
- 接口测试第14讲:软件架构的演变
- 接口测试第15 讲:接口测试新技术