【算法】双指针、递归与回溯、排序、查找

⭐️个人主页：@小羊 ⭐️所属专栏：Linux 很荣幸您能阅读我的文章，诚请评论指点，欢迎欢迎 ~

动图描述

持续更新中…

1、双指针

对撞指针：一般用于顺序结构中，也称左右指针。两指针从两端向中间移动，一个指针从最左端开始，另一个从最右端开始，然后逐渐往中间逼近。终止条件一般是两个指针相遇或者错开left == right || left > right。
快慢指针：让两个移动速度不同的指针在数组或链表等序列结构上移动，经典用法有环形链表。如果我们要研究的问题出现循环往复的情况时，均可考虑快慢指针。
滑动窗口：维护一个动态的窗口，在满足某些条件的情况下移动窗口，从而避免重复计算，提高效率。

移动零

移动零

在这里插入图片描述

数组划分，根据某种规则将数组分为不同性质的两块。
这道题中用 l,r 维护一段区间，区间内全都是0。也就是说 l 始终指向的数字就是0。

在这里插入图片描述

class Solution {
public:void moveZeroes(vector<int>& nums) {int l = 0, r = 0;while (r < nums.size()){if (nums[r]) swap(nums[r], nums[l++]);r++;}}
};

复写零

复写零

在这里插入图片描述

快乐数

快乐数

在这里插入图片描述

类似链表中带环的问题，当快慢指针相遇时入环。

class Solution {
public:int func(int m){int sum = 0;while (m){sum += pow(m % 10, 2);m /= 10;}return sum;}bool isHappy(int n) {int slow = n, fast = func(n);while (slow != fast){slow = func(slow);fast = func(func(fast));}return slow == 1;}
};

长度最小的子数组

长度最小的子数组

在这里插入图片描述

dd爱框框

dd爱框框

在这里插入图片描述

#include <bits/stdc++.h>
using namespace std;int main()
{int n, x;cin >> n >> x;vector<int> a(n + 1);for (int i = 1; i <= n; i++)cin >> a[i];int left = -1, right = -1, sum = 0, len = INT_MAX;for (int l = 1, r = 1; r <= n; r++){ sum += a[r]; // 1.进窗口while (sum >= x) // 2.判断{if (r - l + 1 < len){// 3.更新结果left = l, right = r;len = right - left + 1;}sum -= a[l++]; // 4.出窗口}}cout << left << " " << right << endl;return 0;
}