当前位置: 首页 > news >正文

呼和浩特 的网站建设百度seo教程网

呼和浩特 的网站建设,百度seo教程网,网站建设与管理心得,三类人员 网站开发目录 题目:三数之和 1. 题目解析 2. 算法原理 ①. 暴力枚举 ②. 双指针算法 不漏的处理: 去重处理: 固定一个数 a 的优化: 3. 代码实现 Ⅰ. 暴力枚举(会超时 O(N)) Ⅱ.…

目录

题目:三数之和 

1. 题目解析

2. 算法原理

①.  暴力枚举

②.  双指针算法

不漏的处理:

 去重处理:

 固定一个数 a 的优化:

3. 代码实现

Ⅰ.  暴力枚举(会超时 O(N³))

Ⅱ.  双指针算法 (O(N²))


题目:三数之和 

1. 题目解析

题目截图:

 

题目中所述的顺序不重要有两种情况:

  1. 最终选出来的几个三元组里,每个三元组里的数据顺序,是可以不用考虑的。
  2. 最终选出来的几个三元组,三元组的顺序,也是可以不用考虑的。

题目中还要求元素不能相同:

 

 

题目的细节要求也就是:

  • 最终选出来的几个三元组里面的元素是对应不同的 
  • 返回的三元组及其三元组里的数据的顺序不重要。 

  

题目给的示例二就是没有最终结果的情况

 

2. 算法原理

这道题有两种解法:

  • 暴力枚举(但会超时)
  • 双指针算法

①.  暴力枚举

虽然暴力枚举会超时,这里还要介绍一下的,因为双指针解法就是基于暴力枚举进行优化的。

这里方法就是:排序+暴力枚举(从左往右)+去重

 这里排序去重要注意的是:

所以可以换个策略,先对原数组整个排序:

所以,也就是先排序,再暴力枚举(从左往右枚举),再去重。

这样套三个for循环就可以暴力枚举结果了

//伪代码演示
for (int i = 0; i < n;) // 固定一个数a
{for (int j = i + 1; j < n;)     //依次固定枚举第二个数{for (int k = j + 1; k < n;)    //枚举第三个数{//查找符合的三元组,去重...}}}

 (这里去重在下面双指针解法解释),这里套了三个for循环时间复杂度:O(N³)。

②.  双指针算法

这里双指针算法的解决方法就是:排序+双指针+去重

排序同上面暴力枚举,都先对一整个数组排序,再进行下面的处理。

这里举例一个已经排过序的新数组:

我们先固定一个数,这里先固定第一个数:

这里就转化成了和为s的两个数的问题,这里的s就是这个固定的数的相反数。也就是:

 所以这里解决步骤:

  1. 先对整个数组排序
  2. 固定一个数 a(这里有个小优化,后续介绍)
  3. 在该数后面的区间内,利用双指针算法快速找到两个数的和为 -a 的即可。

注意:这里只是找到了符合条件的情况,并没有去重。

接下来就是处理细节问题了,也就是去重确保所有符合条件的情况不落下(后面简称不漏) 。

和为s的两个数(这里会用到,详细介绍在此链接)

不漏的处理:

先控制指针找到符合情况:

这时可以看到是找到符合的情况了: 接下来就需要调整:

所以,也就是找到一种结果之后,不要停(两个指针不停),缩小区间(两指针都向内移动一步),继续寻找符合的情况。

 去重处理:

去重要考虑两种情况:

  1. 找到一种结果之后,left和right指针要跳过重复的元素(这里也就把第一个4给枚举完了)。但这里固定的 a 还是为-4,再继续枚举,是肯定都是重复结果的。
  2. 所以当使用完一次双指针算法后,a也需要跳过重复的元素。

这里去重可能指针会越界,为了避免越界:

这里的越界问题不止对整个数组区间的越界,还有对要用双指针处理的区间可能会越界。

在实现去重代码时需要加个判断条件就可以解决:

要判断处理这个条件,既可避免越界
if(left < right)        
也就判断两个指针是否在相遇前

 固定一个数 a 的优化:

因为我们前面先排序该数组为升序了,所以固定数a就可以仅仅需要保证它≤0即可。 

if (nums[i] > 0)
{break; // 小优化,数a为正数情况不用考虑,是一定不成立的
}

 接下来实现代码。

3. 代码实现

题目链接:三数之和

Ⅰ.  暴力枚举(会超时 O(N³))

class Solution {
public:vector<vector<int>> threeSum(vector<int>& nums) {// 1.排序sort(nums.begin(), nums.end());vector<vector<int>> ret; // 用来存储所有的三元组// 2.暴力枚举int n = nums.size();int i, j, k;for (i = 0; i < n;) // 固定一个数a{for (j = i + 1; j < n;)     //依次固定枚举第二个数{for (k = j + 1; k < n;)    //枚举第三个数{int sum = nums[i] + nums[j] + nums[k];if (sum == 0){ret.push_back({ nums[i],nums[j],nums[k] });}//去重++k;while (k < n && nums[k] == nums[k - 1]) {++k;}}//去重++j;while (j < n && nums[j] == nums[j - 1]) {++j;}}//去重++i;while (i < n && nums[i] == nums[i - 1]) {++i;}}return ret;}
};

提交记录:

测试用例:

 

 

 

 

Ⅱ.  双指针算法 (O(N²))

class Solution {
public:vector<vector<int>> threeSum(vector<int>& nums) {// 1.排序sort(nums.begin(), nums.end());vector<vector<int>> ret; // 用来存储所有的三元组// 2.利用双指针解决int n = nums.size();for (int i = 0; i < n;) // 固定一个数a{if (nums[i] > 0) {break; // 小优化,数a为正数情况不用考虑,是一定不成立的}// 定义left,right,target通过双指针获取相加等于0的组合int left = i + 1, right = n - 1, target = -nums[i];while (left < right) {int sum = nums[left] + nums[right];if (sum > target) {--right;} else if (sum < target) {++left;} else {// 将获取的三元组尾插ret里ret.push_back({nums[i], nums[left], nums[right]});// 将所有的情况获取--不漏,并去重// 缩小区间查找++left;--right;// 去重left和right,注意区间越界问题while (left < right && nums[left] == nums[left - 1]) {++left;}while (left < right && nums[right] == nums[right + 1]) {--right;}}}// 注意去重i++i;while (i < n && nums[i] == nums[i - 1]) {++i;}}return ret;}
};

注:这里时间复杂度是O(N²)。 

提交记录:

 

 制作不易,若有不足之处或出问题的地方,请各位大佬多多指教 ,感谢大家的阅读支持!!!  

 

http://www.hrbkazy.com/news/21406.html

相关文章:

  • crm系统视频江苏网站seo营销模板
  • 上海高端网站设计百度文库官网登录入口
  • wordpress黑帽插件谷歌seo营销
  • 深圳建设网站费用要看网的域名是多少
  • 怎么做门淘宝网站自己做网站的流程
  • 可视化web网站开发搜索引擎优化不包括
  • 大连城市建设管理局网站百度一下你就知道首页
  • 酒类网站建设方案软文内容
  • wordpress 整站转移成都网站建设公司排名
  • 二级域名分发网站源码大数据营销是什么
  • 中山市做网站网络营销的基本特征
  • 在线单页网站制作google seo教程
  • 做门头上那个网站申报网址注册查询
  • 青海旭云网络做网站需要多少钱电商网络推广怎么做
  • 网络营销 网站媒体资源网官网
  • 电商运营具体是做什么的简述什么是seo及seo的作用
  • 查询域名后缀网站信息流广告公司一级代理
  • 专业的深圳网站建设公司排名枸橼酸西地那非片多长时间见效
  • 网站建设客户需求分析调查表网站和网页的区别
  • 手机网站导航条网络营销策略分析方法
  • 为什么网站建设比商场要贵seo网络培训
  • 新疆 网站建设创意营销案例
  • 做任务赚钱的网站起什么名字好网游推广
  • 西安哪里有做网站的哪有网页设计公司
  • 西宁网站建设报价cu君博规范seo怎么发文章 seo发布工具
  • html自动导入wordpress青岛seo公司
  • 网站开发项目中职责百度网盘免费下载
  • 长垣高端建站北京seo代理计费
  • wordpress获取自定义字段名称班级优化大师app下载学生版
  • 单机游戏大全网站开发整合营销方案案例