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

[C国演义] 第十三章

第十三章

  • 三数之和
  • 四数之和

三数之和

力扣链接

根据题目要求:

  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.lryc.cn/news/183337.html

相关文章:

  • <二>Qt斗地主游戏开发:过场动画的实现
  • 链式法则(Chain Rule)
  • AUTOSAR COM模块框架梳理
  • 详细介绍区块链之挖矿
  • 华为OD机试真题-路灯照明问题(Java/C++/Go/Python)
  • 嵌入式技术面试基本规则
  • osg实现自定义插件读取自定义格式的模型文件到场景
  • redis进阶
  • (一)正点原子STM32MP135移植——准备
  • Kotlin的关键字 lateinit 和 lazy
  • 阿里云服务器ECS详细介绍_云主机_服务器托管_弹性计算
  • 12、建立健全人员培训体系
  • 代码随想录算法训练营第五十九天 | 647. 回文子串 516.最长回文子序列
  • React Redux
  • StreamingLLM - 处理无限长度的输入
  • [Linux 命令] nm 详解
  • 好文学作品的鉴赏标准
  • 智慧公厕:将科技融入日常生活的创新之举
  • ROS(0)命令及学习资源汇总
  • NodeMCU ESP8266开发流程详解(图文并茂)
  • 【最终版】tkinter+matplotlib实现一个强大的绘图系统
  • Postman使用实例
  • 【ES的优势和原理及分布式开发的好处与坏处】
  • Autosar诊断实战系列23-CanTp半/全双工及相关工程问题思考
  • 【Pandas】数据分组groupby
  • 【图像处理GIU】图像分割(Matlab代码实现)
  • Java中的锁与锁优化技术
  • 布局与打包
  • UVa11324 - The Largest Clique
  • 【Linux】TCP的服务端(守护进程) + 客户端