零1.1

朋友们大家好啊从今天开始我将陆续为大家更新关于算法方面的文章如果大家对于算法感兴趣的话欢迎大家订阅我的算法专栏。

双指针算法Two

Algorithm是一种常用的算法技巧通常用于数组、链表或其他线性数据结构中的问题。

该算法使用两个指针在数据结构上进行迭代、搜索或比较以解决特定的问题。

在双指针算法中通常使用两个指针分别称为快指针和慢指针。

快指针和慢指针起始位置通常相同然后根据问题的要求以不同的步长移动指针。

快指针可能会每次移动多个位置而慢指针则每次只移动一个位置。

对撞指针Two

Approach快指针从数组的首部开始慢指针从数组的尾部开始两者向中间移动直到它们相遇或交叉。

这种方法通常用于有序数组中的搜索、求和等问题。

快慢指针Fast

Pointers快指针和慢指针以不同的速度遍历链表。

这种方法通常用于解决链表中的环检测、找到链表中点、链表的反转等问题。

滑动窗口Sliding

Window使用两个指针在数组或字符串上定义一个固定大小的窗口然后根据问题要求移动窗口的起始位置或结束位置。

这种方法通常用于字符串或数组中的子串或子数组问题。

双指针算法的优点在于它的时间复杂度通常较低并且在遍历数据时只需要常量级的额外空间。

它可以有效地降低问题的时间复杂度并且常常用于解决一些数组、链表相关的问题。

1.移动零

https://leetcode.cn/problems/move-zeroes/

1.1

这个题目的目的就是将数组中的所有零给移动到非0数字的右边部分而我们使用双指针就刚好可以将一个数组分为三部分第一部分是非零部分第二部分是数字0第三部分是待移动的部分。

而这三个部分我们使用两个指针

https://leetcode.cn/problems/duplicate-zeros/

2.1

解释调用函数后输入的数组将被修改为[1,0,0,2,3,0,0,4]

输入arr

很多人拿到这个题首先想的是从前往后使用双指针当遇到0的时候将0写两次但是如果这样的话会将后面的数字给覆盖这就会显得很麻烦。

我们不妨换个思路可以先找到复写之后数组的最后一个数字然后从后往前进行数据的写入当遇到0就写两次非0就写一次。

2.从后往前写入数据

arr.length;//1.找到复写之后数组的最后一个数字while(fast

n-1)

break;slow;}//2.调整边界//当fastn的时候说明slow所指的最后一个数字为0if(fast

{arr[n-1]

n-2;slow--;}//3.从后往前写入数据while(slow

{if(arr[slow]

https://leetcode.cn/problems/happy-number/

3.1

对于一个正整数每一次将该数替换为它每个位置上的数字的平方和。

然后重复这个过程直到这个数变为

无限循环

要判断是否为快乐数我们需要知道当我们进行每位数的平方和这个操作的时候最终都会形成一个环。

既然都会形成环那么我们只需要使用快慢指针来找到这个环然后判断这个环是否为1如果是快乐数的话他会在1-1之间形成环而非快乐数就不一定了。

3.3

//这里先将快指针进行一次求和操作防止刚开始就相等了//slow每次进行一次操作fast一次进行两次操作while(slow

fast)

https://leetcode.cn/problems/container-with-most-water/

4.1

[1,8,6,2,5,4,8,3,7]。

在此情况下容器能够容纳水表示为蓝色部分的最大值为

输入height

min(height[left],height[right])。

设置一个变量来存放体积并不断更新这个变量保证这个变量存储的是容积最大的数据。

left

right

容器的宽度⼀定变⼩。

由于左边界较⼩决定了⽔的⾼度。

如果改变左边界新的⽔⾯⾼度不确定但是⼀定不会超过右边的柱⼦⾼度因此容器的容积可能会增⼤。

如果改变右边界⽆论右边界移动到哪⾥新的⽔⾯的⾼度⼀定不会超过左边界也就是不会超过现在的⽔⾯⾼度但是由于容器的宽度减⼩因此容器的容积⼀定会变⼩的

4.3

Math.min(height[left],height[right]);ret

Math.max(v,ret);if(height[left]

height[right])

https://leetcode.cn/problems/valid-triangle-number/

5.1

说的有效的三角形大家应该都不陌生吧任意两边之和大于第三边但是我们真的需要两两组合都判断一遍吗其实并不是的只需要判断两个较短的边之和大于较长的那个边就可以了。

既然知道了只需要判断一次就可以判断是否是有效的三角形所以我们可以先对数组进行一个升序排序从数组的最后开始将它作为三角形的最长的边然后在前面的数组范围内left

left

right、最长的边都可以组合成一个有效的三角形所以以该长度为最长边的三角形的个数为

right

https://leetcode.cn/problems/he-wei-sde-liang-ge-shu-zi-lcof/

6.1

输入一个递增排序的数组和一个数字s在数组中查找两个数使得它们的和正好是s。

如果有多对数字的和等于s则输出任意一对即可。

输入nums

int[]{nums[left],nums[right]};}}return

new

https://leetcode.cn/problems/3sum/

7.1

当直到了如何解决两数之和的问题之后求三数值和其实也很简单还是现将数组以升序的方式排序我们每次固定一个数字然后在剩下的数组中找到和为

target

的值但是真的有这么简单吗注意看题目答案中不可出现重复的三元组什么叫做重复的三元组看第一个示例它等于

target

但是最终输出的结果只有[[-1,-1,2],[-1,0,1]]所以这道题关键难在去重这个问题上那么我们应该如何去重呢当调整

left、right

和那个固定的数字的时候如果所指的数字等于前面的数字那么就跳过。

7.3

ArrayList();Arrays.sort(nums);int

nums.length;int

ArrayList();list1.add(nums[i]);list1.add(nums[left]);list1.add(nums[right]);list.add(list1);left;right--;//去重并且防止越界while(left

right

https://leetcode.cn/problems/4sum/

8.1

输出[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]

输入nums

这个求四数之和如果前面的两数之和和三数之和会做了这个题目也很简单我们只需要先固定一个数字然后在后面的数组内找到和为

target

的三个数就行了唯一需要注意的就是去重。

那么这个题目我就不过多介绍了大家直接看代码就行了。

8.3

nums.length;Arrays.sort(nums);while(i

{int

ArrayList();list1.add(nums[i]);list1.add(nums[j]);list1.add(nums[slow]);list1.add(nums[fast]);list.add(list1);slow;fast--;while(slow

fast