【算法一周目】双指针(2)

目录

有效三角形的个数

解题思路

C++代码实现

和为s的两个数字

解题思路

C++代码实现

三数之和

解题思路

C++代码实现

四数之和

解题思路

C++代码实现


有效三角形的个数

题目链接:611. 有效三角形的个数
题目描述:给定一个包含非负整数的数组nums,返回其中可以组成三角形三条边的三元组个数。

解题思路

首先对于三条边能否构成三角形,其条件就是任意两边之和大于第三边或者任意两边之差小于第三边,也就是说对于任意的正整数a、b、c,如果a + b > c且a + c > b且b + c > a,那么a、b、c就能构成三角形。但是用a、b、c运算3次有点过于冗余,所以需要优化下。

假如a、b、c是有序的也就是a <= b <= c,那么只需要判断a + b > c就能直到能否构成三角形,因为a + b > c成立,c是最大的数,那么a + c > b和b + c > a必然成立。

解法一:排序+暴力求解

先排序,然后用3层for循环枚举所有的三元组。判断是否能构成三角形

class Solution {
public:int triangleNumber(vector<int>& nums) {// 1. 排序sort(nums.begin(), nums.end());int n = nums.size(), ret = 0;// 2. 从小到大枚举所有的三元组for (int i = 0; i < n; i++) {for (int j = i + 1; j < n; j++) {for (int k = j + 1; k < n; k++) {// 当最小的两个边之和大于第三边的时候,统计答案if (nums[i] + nums[j] > nums[k])ret++;}}}return ret;}
};

这样做时间复杂度是O(n ^ 3)必然会超时

解法二:排序+双指针

  • 先对数组排序
  • 固定一个最长边,然后在比这条边小的有序数组种找出一个二元组,使二元组之和大于这个最长边,由于数组有序,可以使用双指针。
  • 设最长边枚举到位置 i ,区间 [left, right]i 位置左边的区间(也就是比它小的区间):
  • 如果 nums[left] + nums[right] > nums[i]:
  • 说明 [left, right - 1] 区间上的所有元素均可以与 nums[right] 构成比 nums[i] 大的二元组。
  • 满足条件的有 right - left 种。
  • 此时 right 位置的元素的所有情况相当于全部考虑完毕right-- 进入下一轮判断
  • 如果 nums[left] + nums[right] <= nums[i]:
  • 说明 left 位置的元素不可能与 [left + 1, right] 位置上的元素构成满足条件的二元组。
  • left 位置的元素可以舍去left++ 进入下一轮循环

 

C++代码实现

class Solution {
public:int triangleNumber(vector<int>& nums) {// 1. 排序sort(nums.begin(), nums.end());//2.双指针int ret = 0;for(int i = nums.size() - 1; i >= 2; --i)  //固定最大数{//利⽤双指针快速统计符合要求的三元组的个数int left = 0, right = i - 1;while(left < right){if(nums[left] + nums[right] > nums[i]){ret += right - left;right--;}else{left++;}}}return ret;}
};

时间复杂度:O(n ^ 2),排序的时间复杂度为 O(n log n),之后每个元素使用双指针进行一次遍历,时间复杂度为 O(n ^ 2)。

空间复杂度:O(log n),排序的栈开销。

和为s的两个数字

题目链接:剑指 Offer 57. 和为s的两个数字
题目描述:输入一个递增排序的数组一个数字 s,在数组中查找两个数,使得它们的和正好是   s。如果有多对数字的和等于 s,则输出任意一对即可

解题思路

解法一:暴力枚举

两层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++) {if (nums[i] + nums[j] == target)return {nums[i], nums[j]};}}return {-1, -1};}
};

解法二双指针

1.初始化left、right指向数组左右两端。

2.当left < right,执行循环。

3.若nums[left] + nums[right] == target,说明找到结果,直接返回

若nums[left] + nums[right] < target当前和小于目标值,需要增大和,left++

若nums[left] + nums[right] > target当前和大于目标值,需要减小和,right--

C++代码实现

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

时间复杂度:O(n)

空间复杂度:O(1)

三数之和

题目链接:15. 三数之和
题目描述:给你一个整数数组 nums,判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k,同时还满足 nums[i] + nums[j] + nums[k] == 0。请你返回所有和为 0 且不重复的三元组。

注意:答案中不可以包含重复的三元组

解题思路

解法:排序+双指针

这道题与双指针类似,可以利用双指针思想来优化暴力枚举。

1.先排序

2.固定一个数a

3.然后在这个数后面的区间内,使用双指针快速找到两个数之和等于 -a

注意,该题是需要有去重操作

1.找到一个结果后left 和 right 指针要跳过重复元素

2.使用完一次双指针后固定的数a也要跳过重复的元素

C++代码实现

class Solution {
public:vector<vector<int>> threeSum(vector<int>& nums) {//1.去重sort(nums.begin(), nums.end());//2.双指针int n = nums.size();vector<vector<int>> vv;for(int i = 0; i < n; ++i)  //固定数{//使用完双指针后的去重操作while(i && i < n && nums[i - 1] == nums[i])i++;if(i == n) break;if(nums[i] > 0) break; //小优化int left = i + 1, right = n - 1;int sum = -1 * nums[i];while(left < right){if(nums[left] + nums[right] > sum)right--;else if(nums[left] + nums[right] < sum)left++;else{vv.push_back({nums[i], nums[left], nums[right]});left++, right--;//left和right跳过重复元素while(left < right && nums[right + 1] == nums[right])right--;while(left < right && nums[left - 1] == nums[left])left++;}}}return vv;}
};

时间复杂度:O(n ^ 2)

空间复杂度:O(log n),排序的栈开销

四数之和

题目链接:18. 四数之和
题目描述:给你一个由 n 个整数组成的数组 nums,和一个目标值 target。请你找出并返回满足下述全部条件且不重复的四元组[nums[a], nums[b], nums[c], nums[d]](若两个四元组元素一一对应,则认为两个四元组重复)

解题思路

解法:排序+双指针

这道题是三数之和的升级版,解法是类似的,注意去重操作就可以的。

1.排序。

2.依次固定一个数a。

3.在a后面的区间利用三数之和找到三个数使得三个数的和等于target - a即可

C++代码实现

class Solution {
public:vector<vector<int>> fourSum(vector<int>& nums, int target) {vector<vector<int>> ans;//1.排序sort(nums.begin(), nums.end());//2.利用双指针解决问题int n = nums.size();for(int i = 0; i < n; i++)  //固定 a{//去重 awhile(i && i < n && nums[i] == nums[i - 1]) i++;if(i == n) break;//三数之和的做法for(int j = i + 1; j < n; j++)  //固定 b{//去重 b while(j != 1 && j < n && j - 1 != i && nums[j] == nums[j - 1])j++;if(j == n) break;int left = j + 1, right = n - 1;long long sum = (long long)target - nums[i] - nums[j];while(left < right){if(nums[left] + nums[right] > sum)right--;else if(nums[left] + nums[right] < sum)left++;else{ans.push_back({nums[i], nums[j], nums[left], nums[right]});left++, right--;// 去重 left 和 rightwhile(left < right && nums[left] == nums[left - 1])left++;while(left < right && nums[right] == nums[right + 1])right--;}    }}    }return ans;}
};

时间复杂度:O(n ^ 3)

空间复杂度:O(log n),排序的栈开销


拜拜,下期再见😏

摸鱼ing😴✨🎞

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/471114.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

基于Python的网上银行综合管理系统

作者&#xff1a;计算机学姐 开发技术&#xff1a;SpringBoot、SSM、Vue、MySQL、JSP、ElementUI、Python、小程序等&#xff0c;“文末源码”。 专栏推荐&#xff1a;前后端分离项目源码、SpringBoot项目源码、Vue项目源码、SSM项目源码、微信小程序源码 精品专栏&#xff1a;…

C++编程技巧与规范-类和对象

类和对象 1. 静态对象的探讨与全局对象的构造顺序 静态对象的探讨 类中的静态成员变量(类类型静态成员) 类中静态变量的声明与定义&#xff08;类中声明类外定义&#xff09; #include<iostream> using namespace std;namespace _nmspl {class A{public:A():m_i(5){…

边缘的检测

边缘检测效果&#xff0c;是一种用于突出图像中的边缘&#xff0c;使物体的轮廓更加明显的图像处理技术&#xff0c;边缘检测的主要目的是找到图像中亮度变化显著的区域&#xff0c;这些区域通常对应于物体的边界&#xff0c;边缘检测相当于利用 Shader 代码自动给屏幕图像进行…

HP G10服务器ESXI6.7告警提示ramdisk tmp已满

物理服务器是HP G10 VCENTER内两台服务器报错提示ramdisk"tmp"已满&#xff0c;无法写入文件 登录ESXI命令行后发现两台主机的/tmp目录都没有空间了 定位到是ams-bbUsg.txt文件占用了大量的空间 1、关闭集群的DRS功能 2、迁移当前主机上面运行的所有虚拟机至其他主…

深度学习中的感受野:从基础概念到多层次特征提取

在深度学习&#xff0c;特别是计算机视觉任务中&#xff0c;感受野&#xff08;Receptive Field&#xff09;是一个至关重要的概念。它指的是在神经网络中某一层的神经元在输入图像上“看到”的区域大小。感受野的大小影响了网络能捕捉的特征层级&#xff0c;从而决定了它的特征…

Diffusion Policy——斯坦福机器人UMI所用的扩散策略:从原理到其编码实现(含Diff-Control、ControlNet详解)

前言 本文一开始是属于此文《UMI——斯坦福刷盘机器人&#xff1a;从手持夹持器到动作预测Diffusion Policy(含代码解读)》的第三部分&#xff0c;考虑后Diffusion Policy的重要性很高&#xff0c;加之后续还有一系列基于其的改进工作 故独立成本文&#xff0c;且写的过程中 …

【数据结构与算法】第12课—数据结构之归并排序

文章目录 1. 归并排序2. 计数排序3. 排序算法复杂度及稳定性分析在这里插入图片描述 1. 归并排序 分治法&#xff08;Divide and Conquer&#xff09;是一种重要的算法设计策略&#xff0c;其核心思想是将一个复杂的大问题分解为若干个小规模的子问题&#xff0c;递归地解决这些…

2024 年 Apifox 和 Postman 对比介绍详细版

Apifox VS Postman &#xff0c;当下流行的的两款 API 开发工具&#xff0c;2024 版对比&#xff01;

vue请求数据报错,设置支持跨域请求,以及2种请求方法axios或者async与await

设置跨域 通过vite创建的项目&#xff0c;一般会在你项目文件中自动生成一个名为vite.config文件&#xff0c;点击添加支持跨域的代码 import { defineConfig } from vite import vue from vitejs/plugin-vue// https://vitejs.dev/config/ export default defineConfig({plu…

【ACM出版】第四届信号处理与通信技术国际学术会议(SPCT 2024)

& 第四届信号处理与通信技术国际学术会议&#xff08;SPCT 2024&#xff09; 2024 4th International Conference on Signal Processing and Communication Technology 2024年12月27-29日 中国深圳 www.icspct.com 第四届信号处理与通信技术国际学术会议&#x…

【大数据学习 | HBASE高级】rowkey的设计,hbase的预分区和压缩

1. rowkey的设计 ​ RowKey可以是任意字符串&#xff0c;最大长度64KB&#xff0c;实际应用中一般为10~100bytes&#xff0c;字典顺序排序&#xff0c;rowkey的设计至关重要&#xff0c;会影响region分布&#xff0c;如果rowkey设计不合理还会出现region写热点等一系列问题。 …

基于微信小程序的农场管理系统的设计与实现,LW+源码+讲解

1.2 课题意义 现如今&#xff0c;信息种类变得越来越多&#xff0c;信息的容量也变得越来越大&#xff0c;这就是信息时代的标志。近些年&#xff0c;计算机科学发展得也越来越快&#xff0c;而且软件开发技术也越来越成熟&#xff0c;因此&#xff0c;在生活中的各个领域&…

学习记录:js算法(九十二):克隆图

文章目录 克隆图思路一 克隆图 给你无向 连通 图中一个节点的引用&#xff0c;请你返回该图的 深拷贝&#xff08;克隆&#xff09;。 图中的每个节点都包含它的值 val&#xff08;int&#xff09; 和其邻居的列表&#xff08;list[Node]&#xff09;。 class Node {public int…

大数据新视界 -- 大数据大厂之 Impala 性能飞跃:动态分区调整的策略与方法(上)(21 / 30)

&#x1f496;&#x1f496;&#x1f496;亲爱的朋友们&#xff0c;热烈欢迎你们来到 青云交的博客&#xff01;能与你们在此邂逅&#xff0c;我满心欢喜&#xff0c;深感无比荣幸。在这个瞬息万变的时代&#xff0c;我们每个人都在苦苦追寻一处能让心灵安然栖息的港湾。而 我的…

win11 新建一个批处理,双击查看本机的IP地址

1、先上个图&#xff1a; 2、bat的代码&#xff1a; :: 获取本机 IP 地址 &#xff1a; 只显示ip echo off for /f "tokens2 delims:" %%a in (ipconfig ^| findstr /i "IP 地址") do set IP%%a echo %IP%pause 3、新建一个文件比如叫ip.bat&#xff0c;…

Spring高手之路26——全方位掌握事务监听器

文章目录 1. 什么是Spring事务监听器&#xff1f;2. 通过TransactionSynchronization 接口实现事务监听器3. 时序图&#xff1a;通过TransactionSynchronization 接口实现事务监听器4. TransactionalEventListener注解实现事务监听器5. 时序图&#xff1a;TransactionalEventLi…

QQ 小程序已发布,但无法被搜索的解决方案

前言 我的 QQ 小程序在 2024 年 8 月就已经审核通过&#xff0c;上架后却一直无法被搜索到。打开后&#xff0c;再在 QQ 上下拉查看 “最近使用”&#xff0c;发现他出现一下又马上消失。 上线是按正常流程走的&#xff0c;开发、备案、审核&#xff0c;没有任何违规&#xf…

MFC工控项目实例二十九主对话框调用子对话框设定参数值

在主对话框调用子对话框设定参数值&#xff0c;使用theApp变量实现。 子对话框各参数变量 CString m_strTypeName; CString m_strBrand; CString m_strRemark; double m_edit_min; double m_edit_max; double m_edit_time2; double …

C语言 | Leetcode C语言题解之第556题下一个更大元素III

题目&#xff1a; 题解&#xff1a; int nextGreaterElement(int n){int x n, cnt 1;for (; x > 10 && x / 10 % 10 > x % 10; x / 10) {cnt;}x / 10;if (x 0) {return -1;}int targetDigit x % 10;int x2 n, cnt2 0;for (; x2 % 10 < targetDigit; x2…

elementui el-table中给表头 el-table-column 加一个鼠标移入提示说明

前言 在使用el-table 表格中有些表格的表头需要加入一些提示&#xff0c;鼠标移入则出现提示&#xff0c;非常实用&#xff0c;我是通过el-table中的el-tooltip实现的&#xff0c;以下的效果预览 代码实现 <el-table ref"multipleTable" :data"data"…