【算法】【优选算法】双指针（下）

news/2024/11/8 15:29:18/

目录

  • 一、611.有效三⻆形的个数
    • 1.1 左右指针解法
    • 1.2 暴力解法
  • 二、LCR 179.查找总价格为目标值的两个商品
    • 2.1 左右指针解法
    • 2.2 暴力解法
  • 三、15.三数之和
    • 3.1 左右指针解法
    • 3.2 暴力解法
  • 四、18.四数之和
    • 4.1 左右指针解法
    • 4.2 暴力解法

一、611.有效三⻆形的个数

题目链接：611.有效三⻆形的个数
题目描述：

题目解析：

  • 返回能够成三角形的三元组合的个数；
  • 三元组合内容相同，但是是原数组中不同的下标的元素，这样的三元组在这道题中是不相同的，要计数。

1.1 左右指针解法

解题思路：

  • 因为我们能构成三角形的证明是两条最小边的和大于最大边，所以我们先将数组排序。
  • 排序后，我们只需要固定一条边，然后使用左右指针在[0, 最大边）区间中去搜索符合条件的边即可。
  • 固定的一条边必须是最大边，因为固定最大边的时候，要让另两边之和变大和变小只有一种走法（即变大左指针向后，变小右指针向前），如果固定最小边，让两边之差变小有两种走法（变小左指针向后和右指针向前都行）。
  • 当左右指针元素和小于最大边，我们只需要将左指针向后走，让元素和更大即可。
  • 当左右指针元素和大于最大边，现在[左指针，右指针) 中的元素和右指针的元素都可以构成三角形了。直接将其中元素个数添加到ret结果中，然后让右指针向前走，让元素和减小即可。

解题代码：

java">//时间复杂度O(n^2)
//空间复杂度O(logn)
import java.util.*;
class Solution {public int triangleNumber(int[] nums) {Arrays.sort(nums);int ret = 0;for(int i = nums.length - 1; i > 0; i--) {int left = 0;int right = i - 1;while(left < right) {if(nums[right] + nums[left] > nums[i]) {ret += right - left;right--;} else {left++;}}}return ret;}
}

1.2 暴力解法

解题思路：
直接使用三次for循环，将每一种构成三角形的可能都枚举出来，然后一一判断是否符合构成三角形的条件即可。但是这种方法时间复杂度过大，会超时。

解题代码：

java">//时间复杂度O(n^3)
//空间复杂度O(1)
import java.util.*;
class Solution {public int triangleNumber(int[] nums) {int ret = 0;int n = nums.length;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] > 2 * Math.max(nums[i],Math.max(nums[j],nums[k]))) {ret++;}}}}return ret;}
}

二、LCR 179.查找总价格为目标值的两个商品

题目链接：LCR 179.查找总价格为目标值的两个商品
题目描述：

题目解析：

  • 数组是有序的，只需要找到一组数组中下标不同的两个数的和为target的返回该组合即可。

2.1 左右指针解法

解题思路：

  • 因为数组是有序的，我们可以利用两数的和的单调性来解题。
  • 我们初始左指针指向第一个元素，右指针指向最后一个元素。两个元素的和的单调性具有规律，让和变大让左指针向后移动，让和变小让右指针向前。

解题代码：

java">//时间复杂度O(n)
//空间复杂度O(1)
import java.util.*;
class Solution {public int[] twoSum(int[] price, int target) {int left = 0, right = price.length-1; while(left < right) {if(price[left] + price[right] > target) right--;else if(price[left] + price[right] < target) left++;else return new int[]{price[left],price[right]};}return null;}
}

2.2 暴力解法

解题思路：

  • 我们直接使用两层for循环将不同的下标的两个元素的和枚举出来比较即可。
  • 但是时间复杂度过大，会超出时间限制。
    解题代码：
java">//时间复杂度O(n^2)
//空间复杂度O(1)
import java.util.*;
class Solution {public int[] twoSum(int[] price, int target) {for(int i = 0; i < price.length; i++) {for(int j = 0; j < price.length; j++) {if(price[i] + price[j] == target) {return new int[]{price[i],price[j]};}}}return null;   }
}

三、15.三数之和

题目链接：15.三数之和
题目描述：

题目解析：

  • 数组中三个元素和为0，并且要求其中的元素不能重合，对三元组中先后顺序也没有要求。

3.1 左右指针解法

解题思路：

  • 当我们固定了一个数之后，是不是就是求另两个数的和等于这个固定的数的相反值，这就跟上一道题的思路差不多了，其实也跟第一题三角形思路也相似。
  • 这道题给我们的数组是无序的，这样我们固定一个数之后，我们来求另两个数和时，单调性的控制就不是唯一的，所以我们要将数组排序。
  • 我们使用一个for-i循环先固定一个数，然后使用左右指针在[i+1，nums.length-1] 区间中去三数之和等于0的数，然后将三元组放进结果集，并且左右指针同时移动一步；比0小就左指针向后走让和变大；比0大就右指针向前走。
  • 去重思路：
    • 思路一：
      • 在判断元素和前去重，由于我们数组是有序的，那么相同数值的元素肯定是在一起的，那么我们只要判断移动后的元素与前一步每移动时的值是否相同即可，当相同再次移动到不同即可。
      • 但是这里面有细节问题：当我们使用这样的方法的时候，我们是直接将所有相同的直接跳过，所以我们有可能跳过初始值（也就是i == 0 left == i+1 right == nums.length-1），就如数组是这样[2, 2, 3 ,2]，当i = 0 时会跳过直接到第三个元素。所有在while循环条件要加上判断是初始值的条件
      • 还有越界风险：所以在while判断的循环中还要将越界风险排除。
      • 还有我们不知道出判断循环的原因是上面是哪个原因哪一个，所以我们在出来判断循环之后，还要判断是否已经越界或者不符合条件，也就是i >= nums.length 和 left >= right。
    • 思路二：
      • 我们在判断和之后去重，只需要考虑越界风险，和相等即可。但是由于在判断和之中，我们要先将i++ 再去去重，去重后已经到了下一个要进循环的元素了, 所以我们for循环中就不要i++了。
  • 小优化：在这道题中是判断和为0，所以我们当nums[i] > 0，后续[i+1，nums.length-1]空间都是正数，不可能还有结果了，直接出循环。

解题代码

java">//时间复杂度O(n^2)
//空间复杂度O(logn)
写法一：
import java.util.*;
class Solution {public List<List<Integer>> threeSum(int[] nums) {List<List<Integer>> ret = new ArrayList<>();Arrays.sort(nums);int len = nums.length;for(int i = 0; i < len; i++) {if(nums[i] > 0) break;//对i去重while(i != 0 && i < len && nums[i] == nums[i - 1]) i++;if(i >= len) break;int left = i + 1;int right = len - 1;while(left < right) {while(left < right && left != i+1 && nums[left] == nums[left-1]) left++;//对left去重while(left < right && right != len-1 && nums[right] == nums[right+1]) right--;//对right去重if(left >= right) break;if(nums[left] + nums[right] < -nums[i]) left++;else if(nums[left] + nums[right] > -nums[i]) right--; else ret.add(Arrays.asList(nums[i],nums[left++],nums[right--]));}}return ret;}
}写法二：
import java.util.*;
class Solution {public List<List<Integer>> threeSum(int[] nums) {List<List<Integer>> ret = new ArrayList<>();Arrays.sort(nums);int len = nums.length;for(int i = 0; i < len; ) {if(nums[i] > 0) break;int left = i + 1;int right = len - 1;while(left < right) {if(nums[left] + nums[right] < -nums[i]) left++;else if(nums[left] + nums[right] > -nums[i]) right--; else { ret.add(Arrays.asList(nums[i],nums[left++],nums[right--]));while(left < right && nums[left] == nums[left-1]) left++;//对left去重while(left < right && nums[right] == nums[right+1]) right--;//对right去重}}//对i去重i++;while(i < len && nums[i] == nums[i - 1]) i++;}return ret;}
}

3.2 暴力解法

解题思路：

  • 我们直接使用三层for循环将每一个三元组枚举出来即可。
  • 去重时我们直接使用HashSet这个集合类即可，所以我们要先将nums排序。
  • 但是会超时。
    解题代码：
java">//时间复杂度O(n^3)
//空间复杂度O(logn)
import java.util.*;
class Solution {public List<List<Integer>> threeSum(int[] nums) {Arrays.sort(nums);List<List<Integer>> ret = new ArrayList<>();Set<List<Integer>> set = new HashSet<>();int len = nums.length;for(int i = 0; i < len; i++) {for(int j = i+1; j < len; j++) {for(int k = j+1; k < len; k++) {if(nums[i] + nums[j] + nums[k] == 0) {set.add(Arrays.asList(nums[i],nums[j],nums[k]));}}}}ret.addAll(set);return ret;}
}

四、18.四数之和

题目链接：18.四数之和
题目描述：

题目分析：
跟上面的三数之和，思路一样，代码雷同，只是需要固定两个数即可。

4.1 左右指针解法

解题思路：

  • 思路参考上一道三数之和，两个细节：
  • 这道题有例子是会超过int的最大值的，所以我们需要在计算和的时候使用long来储存。

    解题代码：
java">//时间复杂度O(n^3)
//空间复杂度O(logn)
写法一：
import java.util.*;
class Solution {public List<List<Integer>> fourSum(int[] nums, int target) {Arrays.sort(nums);List<List<Integer>> ret = new ArrayList<>();int len = nums.length;for(int i = 0; i < len; i++) {//对i去重while(i < len && i != 0 && nums[i] == nums[i-1]) i++;if(i >= len ) break;for(int j = i+1; j < len; j++) {//对j去重while(j < len && j != i+1 && nums[j] == nums[j-1]) j++;if(j >= len ) break;long newTarget = (long)target - nums[i] - nums[j];int left = j + 1;int right = len - 1;while(left < right) {while(left < right && left != j+1 && nums[left] == nums[left-1]) left++;//对left去重while(left < right && right != len-1 && nums[right] == nums[right+1]) right--;//对right去重if(left >= right) break;long sum = (long)nums[left] + nums[right];if(sum > newTarget) right--;else if(sum < newTarget) left++;else ret.add(Arrays.asList(nums[i],nums[j],nums[left++],nums[right--]));}}}return ret;}
}
写法二：
import java.util.*;
class Solution {public List<List<Integer>> fourSum(int[] nums, int target) {Arrays.sort(nums);List<List<Integer>> ret = new ArrayList<>();int len = nums.length;for(int i = 0; i < len;) {for(int j = i+1; j < len;) {long newTarget = (long)target - nums[i] - nums[j];int left = j + 1;int right = len - 1;while(left < right) {long sum = (long)nums[left] + nums[right];if(sum > newTarget) right--;else if(sum < newTarget) left++;else {ret.add(Arrays.asList(nums[i],nums[j],nums[left++],nums[right--]));while(left < right && nums[left] == nums[left-1]) left++;//对left去重while(left < right && nums[right] == nums[right+1]) right--;//对right去重}}//对j去重j++;while(j < len && nums[j] == nums[j-1]) j++;}i++;//对i去重while(i < len && nums[i] == nums[i-1]) i++;}return ret;}
}

4.2 暴力解法

解题思路：

  • 4层for循环，HashSet去重。
  • 会超时。

解题代码：

java">//时间复杂度O(n^4)
//空间复杂度O(logn)
import java.util.*;
class Solution {public List<List<Integer>> fourSum(int[] nums, int target) {Arrays.sort(nums);List<List<Integer>> ret = new ArrayList<>();Set<List<Integer>> set = new HashSet<>();int len = nums.length;for(int i = 0; i < len; i++) {for(int j = i+1; j < len; j++) {for(int k = j+1; k < len; k++) {for(int n = k+1; n < len; n++){if((long)nums[i] + nums[j] + nums[k] + nums[n] == target) {set.add(Arrays.asList(nums[i],nums[j],nums[k],nums[n]));}}}}}ret.addAll(set);return ret;}
}

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

相关文章

debian11安装最新rabbitmq

debian11安装最新rabbitmq

1、使用官网提供系统对应的安装脚本 安装 版本说明&#xff1a; Debian Buster代表Debian 10 Debian Bullseye代表Debian 11 Debian Bookworm代表Debian 12 ‌Debian Trixie代表Debian 13 Debian Sid代表Debian unstable版本 2、新建脚本文件 vim rabbitMq.sh将脚本内容复制到…
阅读更多...
python操作CSV和excel,如何来做?

python操作CSV和excel,如何来做?

诸如pandas、xlrd、xlwings也可以实现excel的读取&#xff0c;但pandas最简单实用。 使用pandas分三步走&#xff1a; 1、安装python 2、安装IDE比如pycharm、jupyter&#xff08;这里强烈推荐使用jupyter notebook或者lab&#xff09; notebook展示数据很直观&#xff0c;就…
阅读更多...
LabVIEW VISA通信常见问题

LabVIEW VISA通信常见问题

在工业自动化和测试测量等应用中&#xff0c;使用LabVIEW的VISA函数与设备进行通信时&#xff0c;若发送指令后未能接收数据&#xff0c;以下因素可能是原因&#xff1a; 设备未响应或响应延迟应用示例&#xff1a;例如&#xff0c;在控制测量仪器&#xff08;如电压表&#xf…
阅读更多...
深入理解torch.functional.cross_entropy或F.cross_entropy的原理

深入理解torch.functional.cross_entropy或F.cross_entropy的原理

参考Trying to understand cross_entropy loss in PyTorch的回答&#xff1a; 可知以下两个调用等价&#xff1a; import torch import torch.nn.functional as F x torch.FloatTensor([[1.,0.,0.],[0.,1.,0.],[0.,0.,1.]]) y torch.LongTensor([0,1,2])print(torch.nn.fun…
阅读更多...
Hive 的数据类型

Hive 的数据类型

基本类型 整型 TINYINT: 1字节整数&#xff0c;范围从 -128 到 127。SMALLINT: 2字节整数&#xff0c;范围从 -32,768 到 32,767。INT: 4字节整数&#xff0c;范围从 -2,147,483,648 到 2,147,483,647。BIGINT: 8字节整数&#xff0c;范围从 -9,223,372,036,854,775,808 到 9…
阅读更多...
无人机之中继通信技术篇

无人机之中继通信技术篇

一、定义与原理 无人机中继通信技术是指通过无人机搭载中继设备&#xff0c;将信号从一个地点传输到另一个地点&#xff0c;从而延长通信距离并保持较好的通信质量。其原理类似于传统的中继通信&#xff0c;即在两个终端站之间设置若干中继站&#xff0c;中继站将前站送来的信号…
阅读更多...
PHP-FPM 性能配置优化

PHP-FPM 性能配置优化

PHP-FPM 性能配置优化 4 核 8 G 服务器大约可以开启 500 个 PHP-FPM&#xff0c;极限吞吐量在 580 qps &#xff08;Query Per Second 每秒查询数&#xff09;左右。 Nginx php-fpm 是怎么工作的&#xff1f; php-fpm 全称是 PHP FastCGI Process Manager 的简称&#xff0c;…
阅读更多...
Linux驱动开发（3）：字符设备驱动

Linux驱动开发（3）：字符设备驱动

上一章节我们了解到什么是内核模块&#xff0c;模块的加载卸载详细过程以及内核模块的使用等内容。 本章&#xff0c;我们将学习驱动相关的概念&#xff0c;理解字符设备驱动程序的基本框架&#xff0c;并从源码上分析字符设备驱动实现和管理。 主要内容有如下五点&#xff1a;…
阅读更多...
最新文章

Copyright @ 2022~2023