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

【算法一周目】双指针(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.mrgr.cn/news/75111.html

相关文章:

  • SELinux知识点
  • CPU详细介绍
  • Linux之vim模式下全选命令
  • 线性回归 - 最小二乘法
  • K8S资源限制之LimitRange
  • Rust:原子操作 AtomicBool
  • JavaScript总结
  • Path.Combine容易被忽略的细节
  • DAPP迎启动契机,Scroll 生态全面启动为 Pencils Protocol 赋能
  • C++函数的返回值在内存中的传递过程
  • 第4章-计划 4.4 范围管理
  • Python基础学习-07不可重复的set集合
  • 常用的生物医药专利查询数据库及网站(很全!)
  • Jetpack 之 Ink API初探
  • qt QQuickView详解
  • 《DPT: Deformable Patch-based Transformer for Visual Recognition》论文翻译
  • Go常见框架对比
  • AI驱动的电商创新:提升销售效率与用户体验
  • session 的工作原理
  • SpringBoot(十)SpringBoot使用QQ邮箱stmp发送邮件
  • 【计算机网络】UDP网络程序
  • 大数据新视界 -- 大数据大厂之 Impala 存储格式转换:从原理到实践,开启大数据性能优化星际之旅(下)(20/30)
  • 一个免费的Java 应用内存问题分析工具,用于 OutOfMemoryErrors 和堆大小调整等问题(带私活源码)
  • 基于51单片机智能窗帘仿真设计
  • 解决failed to execute PosixPath(‘dot‘) 或者GraphViz‘s executables not found
  • 【MySQL】约束