网站备案信息核验单填写,网站中怎么做视频直播,结构优化设计,高性能网站开发个人主页#xff1a;手握风云 专栏#xff1a;算法 目录
一、双指针算法思想
二、算法题精讲
2.1. 查找总价格为目标值的两个商品
2.2. 盛最多水的容器
编辑
2.3. 移动零
2.4. 有效的三角形个数 一、双指针算法思想 双指针算法主要用于处理数组、链表等线性数据结构… 个人主页手握风云 专栏算法 目录
一、双指针算法思想
二、算法题精讲
2.1. 查找总价格为目标值的两个商品
2.2. 盛最多水的容器
编辑
2.3. 移动零
2.4. 有效的三角形个数 一、双指针算法思想 双指针算法主要用于处理数组、链表等线性数据结构中的问题。它通过设置两个指针在数据结构上进行遍历和操作从而实现高效解决问题。
二、算法题精讲
2.1. 查找总价格为目标值的两个商品 我们优先想到的是暴力解法利用两层for循环来检验两个数的和是否为目标值。那么此时的时间复杂度为。
class Solution {public int[] twoSum(int[] price, int target) {int len price.length;for(int i0;ilen;i){for(int ji1;jlen;j){if(price[i]price[j] target){return new int[]{price[i],price[j]};}}}return new int[0];}
} 但题目当中给出数组是按照升序排列的那么我们就可以利用单调性定义左右两个指针来遍历数组。我们先定义一个sum变量sum的值等于左右指针所指的值之和。然后通过sum与target的比较如果sum小于target则左指针向右移动如果sum大于target则右指针向左移动如果sum等于target则返回两个数。 完整代码实现
class Solution {public int[] twoSum(int[] price, int target) {int len price.length;int left 0,right len-1;while(left right){int sum price[left] price[right];if(sum target){left;} else if (sum target) {right--;}else{return new int[]{price[left],price[right]};}}return new int[0];}
}
2.2. 盛最多水的容器 首先我们得明白如何计算容器的体积容器的底就可以用两个数组的下标相减得到容器的高根据木桶效应是数组中最小的元素。我们先选左右边界来作为容器此时我们记容器体积为v1如果left指针向右移动则容器的底一定在减小如果遇到比左边界小的数那么高就会减小如果遇到比左边界大的数那么高不变。所以容器的体积一定是在减小。此时我们就可以把左边界干掉left向右移动得到新的容器体积v2根据上面的逻辑我们同理可以把右边界干掉。以此类推直到找出最大的容器体积。 class Solution {public int maxArea(int[] height) {int len height.length;int left 0,right len-1,ret 0;while(left right){int v Math.min(height[left], height[right]) * (right-left);ret Math.max(ret,v);if(height[left] height[right]){left;}else{right--;}}return ret;}
}
2.3. 移动零 本题要求在不复制数组的情况下原地对数组进行操作。我们先定义cur和dest两个指针cur指针的作用是先扫描数组将数组分为已处理和待处理的两个区间dest指针是将已处理的区间变为非零区间和零区间。当cur遇到零元素时不做任何处理直接让cur向右移动一位当cur遇到非零元素时先让dest向右移动一位再让两个指针所指向的值进行交换。直到cur遍历完整个数组 完整代码实现
public class Solution {public void moveZeroes(int[] nums){for (int cur 0,dest -1; cur nums.length; cur) {if(nums[cur] ! 0){dest;int temp nums[cur];nums[cur] nums[dest];nums[dest] temp;}}}
}
2.4. 有效的三角形个数 要找到有效的三角形个数就是在数组中找到能够构成三角形的三元子数组。我们首先想到的暴力解法利用三层for循环来查找此时的时间复杂度为。 对于三条边的比较我们只需要让三角形较小的两条边之和与最大的边进行比较即可。要想得到最大值首先我们可以先对数组进行一个排序使数组呈升序排列。排序之后先固定右侧的最大值在定义left和right两个指针让right指针指向被固定值的左侧。如果两个元素之和大于最大值那么left指针向右移动两个元素之和一定会大于最大值此时我们就可以干掉右指针所指向的数如果两个元素之和小于等于最大值那么right指针向左移动两个元素之和一定会小于等于最大值此时我们就可以干掉左指针所指向的数。完成之后我们就可以将固定值向左移动在进行上述操作直到固定数组的第三个元素。 完整代码实现
class Solution {public int triangleNumber(int[] nums) {Arrays.sort(nums);//排序优化int ret 0,len nums.length;for (int i len-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;}
}
