基础数学二两数:和 三数:和
目录
两数之和_牛客题霸_牛客网
给出一个整型数组 numbers 和一个目标值 target,请在数组中找出两个加起来等于目标值的数的下标,返回的下标按升序排列。
(注:返回的数组下标从1开始算起,保证target一定可以由数组里面2个数字相加得到)
数据范围:2≤len(numbers)≤1052≤len(numbers)≤105,−10≤numbersi≤109−10≤numbersi≤109,0≤target≤1090≤target≤109
要求:空间复杂度 O(n)O(n),时间复杂度 O(nlogn)O(nlogn)
【解法一】枚举遍历 无法通过
-
-
class Solution {
-
public:
-
vector<int> twoSum(vector<int>& numbers, int target) {
-
// write code here
-
vector<int> res;
-
int n = numbers.size();
-
for(int i = 0; i < n; i )
-
{
-
for(int j = i 1; j < n; j )
-
{
-
if(numbers[i] numbers[j] == target)
-
{
-
res.push_back(i 1);
-
res.push_back(j 1);
-
return res;
-
}
-
}
-
}
-
return res;
-
}
-
};
【解法二】哈希存储
这道题让我对哈希表又有了新的认知,之前每次都是用hash来进行一个数出现的次数,于是会写出这样的 mp[arr[i]] 表示这个数出现的次数加一,然而这道题把数与其在number中所对应的下标对应着存入map中。然后在后续遍历中,如果target-number[i]在map中存在可以直接返回我所需要的下标值。
时间复杂度O(N) 只需遍历一次数组,每次在哈希表中查找的时间复杂度为O(1)
空间复杂度为O(N) 创建map
-
class Solution {
-
public:
-
vector<int> twoSum(vector<int>& numbers, int target) {
-
// write code here
-
vector<int> res;
-
map<int, int> mp;
-
int n = numbers.size();
-
for(int i = 0; i < n; i )
-
{
-
int temp = target - numbers[i];
-
if(mp.find(temp) == mp.end())
-
mp[numbers[i]] = i;
-
else{
-
res.push_back(mp[temp] 1);
-
res.push_back(i 1);
-
break;
-
}
-
}
-
return res;
-
}
-
};
三数之和_牛客题霸_牛客网
给出一个有n个元素的数组S,S中是否有元素a,b,c满足a b c=0?找出数组S中所有满足条件的三元组。
数据范围:0≤n≤10000≤n≤1000,数组中各个元素值满足 ∣val∣≤100∣val∣≤100
空间复杂度:O(n2)O(n2),时间复杂度 O(n2)O(n2)
注意:
- 三元组(a、b、c)中的元素必须按非降序排列。(即a≤b≤c)
- 解集中不能包含重复的三元组。
将三数求和转化为二数求和来达到解题的目的,使用set接口进行去重。
-
class Solution {
-
public:
-
vector<vector<int>> TwoSum(vector<int> num, int target, int begin)
-
{
-
int n = num.size();
-
vector<vector<int>> res; // 用来返回结果数组
-
for(int i = begin; i < n; i )
-
{
-
int _target = target-num[i]; // 将二数求和转化为找一个数
-
if(find(num.begin() i 1,num.end(),_target) != num.end())
-
{
-
// 利用#include<algorithm> 中find接口来进行查找
-
// 找不到就返回num的end()
-
vector<int> temp;
-
temp.push_back(num[i]); //如果找到了就把第二个数与第三个数都放入temp中
-
temp.push_back(_target);
-
res.push_back(temp); //完成一次结果并放入res中,继续后续其他结果的查找
-
}
-
}
-
return res;
-
}
-
vector<vector<int> > threeSum(vector<int> &num) {
-
set<vector<int>> res; // 用来去重的set容器
-
vector<vector<int>> Res; // 用来返回结果
-
int n = num.size();
-
if(n<3)return Res; // 元素个数小于三个返回空
-
sort(num.begin(), num.end()); // 进行一次排序整理
-
for(int i = 0; i < n; i )
-
{
-
int target = 0-num[i]; // 把三数之和转化为俩数之和
-
vector<vector<int>> temp = TwoSum(num, target, i 1); // 多传一个下标参数 防止重复
-
if(!temp.empty())
-
{
-
for(auto e : temp)
-
{
-
e.insert(e.begin(), num[i]); // 在每组返回的数组最前方插入第一个数
-
res.insert(res.end(), e); // 将三个数的数组放入到set容器中进行去重
-
}
-
}
-
}
-
for(auto e : res)
-
Res.push_back(e); // 将set转移至Res中。
-
return Res;
-
}
-
};
这篇好文章是转载于:学新通技术网
- 版权申明: 本站部分内容来自互联网,仅供学习及演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系,请提供相关证据及您的身份证明,我们将在收到邮件后48小时内删除。
- 本站站名: 学新通技术网
- 本文地址: /boutique/detail/tanhieegec
系列文章
更多
同类精品
更多
-
photoshop保存的图片太大微信发不了怎么办
PHP中文网 06-15 -
photoshop扩展功能面板显示灰色怎么办
PHP中文网 06-14 -
word里面弄一个表格后上面的标题会跑到下面怎么办
PHP中文网 06-20 -
《学习通》视频自动暂停处理方法
HelloWorld317 07-05 -
TikTok加速器哪个好免费的TK加速器推荐
TK小达人 10-01 -
Android 11 保存文件到外部存储,并分享文件
Luke 10-12 -
excel下划线不显示怎么办
PHP中文网 06-23 -
微信公众号没有声音提示怎么办
PHP中文网 03-31 -
微信运动停用后别人还能看到步数吗
PHP中文网 07-22 -
excel打印预览压线压字怎么办
PHP中文网 06-22