[C国演义] 第十三章

news/2024/2/27 22:45:30

第十三章

  • 三数之和
  • 四数之和

三数之和

力扣链接

根据题目要求:

  1. 返回的数对应的下标各不相同
  2. 三个数之和等于0
  3. 不可包含重复的三元组 – – 即顺序是不做要求的
    如: [-1 0 1] 和 [0, 1, -1] 是同一个三元组
  4. 输出答案顺序不做要求

暴力解法: 排序 + 3个for循环 + 去重 — — N^3, 肯定超时
优化: 排序 + 双指针 + 去重 — — N^2
优化的具体思路:
固定一个数, 记作a; 在剩余的空间里面找和为 -a的两个数(由于是排好序的, 所以使用双指针)
去重有两种方法:
1.set去重
2 在循环内部缩小空间 — — 非常值得我们去尝试

  1. set去重
class Solution {
public:vector<vector<int>> threeSum(vector<int>& nums) {// 排序sort(nums.begin(), nums.end());// 记录结果vector<vector<int>> res; // 固定一个数 + 双指针int n = nums.size();for(int i = 0; i < n; i++) // 固定一个数{// 双指针优化int left = i+1, right = n-1;int targt = -nums[i];while(left < right){int sum = nums[left] + nums[right];if(sum < targt){left++;}else if(sum > targt){right--;}else{res.push_back({nums[i], nums[left], nums[right]});left++;right--;}}}// 去重set<vector<int>> result(res.begin(), res.end());res.clear();for(auto e : result){res.push_back(e);}return res;}
};


上面的运行结果太慢了, 我们尝试一下 缩小空间去重👇👇👇

  1. 缩小空间去重
class Solution {
public:vector<vector<int>> threeSum(vector<int>& nums) {// 排序sort(nums.begin(), nums.end());// 记录结果vector<vector<int>> res; // 固定一个数 + 双指针int n = nums.size();for(int i = 0; i < n;) // 固定一个数{// 双指针优化int left = i+1, right = n-1;int targt = -nums[i];while(left < right){int sum = nums[left] + nums[right];if(sum < targt){left++;}else if(sum > targt){right--;}else{res.push_back({nums[i], nums[left], nums[right]});left++;right--;// 去重left 和 rightwhile(left < right && nums[left] == nums[left-1])  left++;while(right > left && nums[right] == nums[right+1])  right--;}}// 去重ii++;while(i < n && nums[i] == nums[i-1])  i++;}return res;}
};



四数之和

力扣链接

这一题就跟上面的题目相似, 思路也很相似: 排序 + 固定两个数, 双指针优化 + 去重. 当然, 我们这里的去重逻辑也是 缩小空间去重

class Solution {
public:vector<vector<int>> fourSum(vector<int>& nums, int target) {sort(nums.begin(), nums.end());vector<vector<int>> res;int n = nums.size();// 选定一个数, 内部用三数之和for(int i = 0; i < n;){// 选定一个数, 内部使用双指针优化for(int j = i+1; j < n;){int left = j+1, right = n-1;long int tar = target - (long int)(nums[i]+nums[j]);while(left < right){long int cur = nums[left] + nums[right];if(cur < tar)  left++;else if(cur > tar)  right--;else{res.push_back({nums[i], nums[j], nums[left], nums[right]});left++, right--;// 去重left 和 rightwhile(left < right && nums[left] == nums[left-1])  left++;while(right > left && nums[right] == nums[right+1])  right--;}}// j的去重j++;while(j < n && nums[j] == nums[j-1])  j++;}// i的去重i++;while(i < n && nums[i] == nums[i-1])  i++;}return res;}
};


号令风霆迅,天声动北陬。
长驱渡河洛,直捣向燕幽。
马蹀阏氏血,旗袅可汗头。
归来报明主,恢复旧神州。 — — [宋] 岳飞 <送紫岩张先生北伐>


http://www.ppmy.cn/news/1137683.html

相关文章

1.7. 找出数组的第 K 大和原理及C++实现

题目 给你一个整数数组 nums 和一个 正 整数 k 。你可以选择数组的任一 子序列 并且对其全部元素求和。 数组的 第 k 大和 定义为&#xff1a;可以获得的第 k 个 最大 子序列和&#xff08;子序列和允许出现重复&#xff09; 返回数组的 第 k 大和 。 子序列是一个可以由其他数…

XFTP上传文件状态出现错误的原因和解决方案

这几天有时候会出现XFTP会出现上传的时候状态出现错误的情况&#xff0c;我没那么在意&#xff0c;但是今天要传比较重要的东西&#xff0c;结果没办法传&#xff0c;我参考了这个方法&#xff0c;但是感觉修改用户组的权限是正确的可能解释的没那准确 之后我是直接把XFTP的登陆…

1.1入门指南(AutoMapper官方文档翻译)

官方文档原文链接 什么是AutoMapper&#xff1f; AutoMapper是一个对象-对象映射器。对象-对象映射的工作原理是将一种类型的输入对象转换为不同类型的输出对象。AutoMapper的有趣之处在于&#xff0c;它提供了一些有趣的约定&#xff0c;将如何将类型A映射到类型B的繁琐工作…

微服务的初步使用

环境说明 jdk1.8 maven3.6.3 mysql8 idea2022 spring cloud2022.0.8 微服务案例的搭建 新建父工程 打开IDEA&#xff0c;File->New ->Project&#xff0c;填写Name&#xff08;工程名称&#xff09;和Location&#xff08;工程存储位置&#xff09;&#xff0c;选…

python中的三元表达式

一. 三元表达式 请看下面的代码,很好理解的,三元表达式会减少我们的代码的使用量.提高简洁性,增加易读性. num1 int(input(请输入第一个数:)) num2 int(input(请输入第二个数:))# if else 获取做大的那个数 if num1 > num2:num_max num1 else:num_max num2 print(num_m…

【Pytorch笔记】3.数学运算

深度之眼官方账号 - 01-03-mp4-张量操作与线性回归 torch.add() 功能&#xff1a;逐元素计算inputalphaother。 torch.add(input,alpha1,other,outNone)input&#xff1a;tensor&#xff1b; alpha&#xff1a;other的系数&#xff0c;是个实数&#xff1b; other&#xff1…

2G大小的GPU对深度学习的加速效果如何?

训练数据情况 总共42776张224*224*3张图片 Found 42776 files belonging to 9 classes. Using 12833 files for training. 模型参数情况 Total params: 10,917,385 Trainable params: 10,860,745 Non-trainable params: 56,640 batch-size:12 GPU信息 NVIDIA GeForce GT 7…

【2023年11月第四版教材】第18章《项目绩效域》(第二部分)

TOC) 6 项目工作绩效域 1、有效执行工作绩效域可以实现预期目标&#xff0c;主要包含:①高效且有效的项目绩效;②适合项目和环境的项目过那益干系人适当的沟通和参与;④对实物资源进行了有效管理;⑤对采购进行了有效管理;⑥有.处理了变更;⑦通过持续学习和过程改进提高了团队…

【2023年11月第四版教材】第18章《项目绩效域》(合集篇)

第18章《项目绩效域》&#xff08;合集篇&#xff09; 1 章节内容2 干系人绩效域2.1 绩效要点2.2 执行效果检查2.3 与其他绩效域的相互作用 3 团队绩效域3.1 绩效要点3.2 与其他绩效域的相互作用3.3 执行效果检查3.4 开发方法和生命周期绩效域 4 绩效要点4.1 与其他绩效域的相互…

【Pandas】Apply自定义行数

文章目录 1. Series的apply方法2. DataFrame的apply方法2.1 针对列使用apply2.2 针对行使用apply Pandas提供了很多数据处理的API,但当提供的API不能满足需求的时候,需要自己编写数据处理函数, 这个时候可以使用apply函数apply函数可以接收一个自定义函数, 可以将DataFrame的行…

集群服务器

文章目录 项目名:实现集群服务器技术栈通过这项目你学到(或者复习到)实现功能编码环境json环境muduo库boost库MySql数据库登录mysql&#xff1a;查看mysql服务开启了没有&#xff1f;mysql的服务器及开发包库chat&#xff0c;表 allgroup friend groupuser offlinemessage user…

C#中的数组探究与学习

目录 C#中的数组一般分为:一.数组定义:为什么要使用数组?什么是数组?C#一维数组for和foreach的区别C#多维数组C#锯齿数组初始化的意义:适用场景:C#中的数组一般分为: ​①.一维数组。 ②.多维数组,也叫矩形数组。 ③.锯齿数组,也叫交错数组。 一.数组定义: 数组…

功能比较:Redisson vs Jedis

Redis最流行的两个Java客户端库是Redisson和Jedis。Redisson提供内存中的数据网格功能&#xff0c;支持Redis的各种分布式对象和服务。另一方面&#xff0c;Jedis是一个更轻量级的产品&#xff0c;它缺乏其他库的某些功能。 如果你正在为Redis寻找一个Java客户端库&#xf…

Python:torch.nn.Conv1d(), torch.nn.Conv2d()和torch.nn.Conv3d()函数理解

Python&#xff1a;torch.nn.Conv1d(), torch.nn.Conv2d()和torch.nn.Conv3d()函数理解 1. 函数参数 在torch中的卷积操作有三个&#xff0c;torch.nn.Conv1d(),torch.nn.Conv2d()还有torch.nn.Conv3d(),这是搭建网络过程中常用的网络层&#xff0c;为了用好卷积层&#xff0…

互联网Java工程师面试题·Elasticsearch 篇·第二弹

12、详细描述一下 Elasticsearch 索引文档的过程。 协调节点默认使用文档 ID 参与计算&#xff08;也支持通过 routing &#xff09;&#xff0c;以便为路由提供合适的分片。 shard hash(document_id) % (num_of_primary_shards) 1 、当分片所在的节点接收到来自协调节点…

QQ登录的具体流程

文章目录 网站授权QQ登录QQ登录的完整流程代码示例1. 添加依赖2. 配置文件3. 实现Service4. 创建Controller 网站授权QQ登录 首先需要去QQ互联申请应用填写网站的相关信息&#xff0c;以及回调地址&#xff0c;需要进行审核。申请流程暂时不说了&#xff0c;百度一下挺多申请失…

【抢先体验】开通使用 ChatGPT 语音版功能保姆级教程

大家好&#xff0c;我是苍何&#xff0c;一个土木转码的非典型程序员&#xff0c;也是一名技术管理者&#xff0c;同时也是 AI 应用的探索者。今天在视频号上看到和 ChatGPT 语音对话的视频&#xff0c;其声音的真实感太让人震撼了&#xff0c;于是也想去抢先体验一下 ChatGPT …

Spring Boot 常用注解详解:全面指南

Spring Boot 中有许多常用的注解&#xff0c;这些注解用于配置、管理和定义 Spring Boot 应用程序的各个方面。以下是这些注解按大类和小类的方式分类&#xff0c;并附有解释和示例。 一、Spring Boot 核心注解 SpringBootApplication 解释&#xff1a;这是一个组合注解&a…

[AOSP] [JNI] [Android] AOSP中使用JNI

一. 简要 &#x1f34e; JNI是Java Native Interface的缩写&#xff0c;它提供了若干的API实现了Java和其他语言的通信&#xff08;主要是C&C&#xff09;。从Java1.1开始&#xff0c;JNI标准成为java平台的一部分&#xff0c;它允许Java代码和其他语言写的代码进行交互。J…

Vmware 静态网络配置

概述 仅主机模式&#xff08;VMware1&#xff09;&#xff1a;使用host-only的方式是不能和外界通信的&#xff0c;只能够和本机的物理网卡通信 桥接&#xff08;VMnet0&#xff09;&#xff1a;使用桥接的方式使得自己的虚拟机和自己的真实机网卡在同一个网段 NAT&#xff0…
最新文章