双指针算法思想——OJ例题扩展算法解析思路
大家好！上一期我发布了关于双指针的OJ平台上的典型例题思路解析，基于上一期的内容，我们这一期从其中内容扩展出来相似例题进行剖析和运用，一起来试一下吧！
目录
一、 基于移动零的举一反三
题一：27. 移除元素 - 力扣（LeetCode）
运行代码：
1. 双指针初始化
2. 遍历数组
3. 处理非 val 元素
4. 处理 val 元素
5. 返回结果
6. 时间复杂度
7. 空间复杂度
代码总结
示例
题二：2460. 对数组执行操作 - 力扣（LeetCode）
基本大体思路：
第一部分：应用特定规则修改数组元素
思路：
示例：
第二部分：将所有非零元素移动到数组的前部
思路：
示例：
第三部分：返回结果——返回修改后的数组 nums。
总结
示例运行
二、基于快乐数的举一反三
题一：2460. 对数组执行操作 - 力扣（LeetCode）
运行代码：
1. 初始化快慢指针
2. 处理特殊情况
3. 遍历链表
4. 遍历结束
5. 算法原理
6. 时间复杂度
7. 示例
8. 总结
题二：258. 各位相加 - 力扣（LeetCode）
运行代码：
2. 内层循环：计算数位和
3. 返回结果
4. 示例
5. 时间复杂度
题三： 263. 丑数 - 力扣（LeetCode）
运行代码：
1. 处理特殊情况
2. 定义质因数数组
3. 循环去除质因数
4. 判断最终结果
总结
题四：1945. 字符串转化后的各位数字之和 - 力扣（LeetCode）
运行代码:
问题分析
代码思路
第一步：字母转换为数字字符串
第二步：数字求和操作
第三步：返回结果
代码实现的关键点
步骤：
时间复杂度分析
题五：2457. 美丽整数的最小增量 - 力扣（LeetCode）
思路：
运行代码：
题六：2507. 使用质因数之和替换后可以取到的最小值 - 力扣（LeetCode）
运行代码：
问题分析
代码思路
第一步：质因数分解
第二步：替换为质因数之和
第三步：返回结果
代码实现的关键点
1. sumOfPrimeFactors 函数
2. smallestValue 函数
示例运行
步骤：
时间复杂度分析
题七：2520. 统计能整除数字的位数 - 力扣（LeetCode）
运行代码：
代码思路
第一步：初始化
第二步：逐位提取数字
第三步：返回结果
代码实现的关键点
1. 逐位提取数字
2. 判断是否能整除
3. 边界条件
示例运行
步骤：
时间复杂度分析
一、 基于移动零的举一反三
题一：27. 移除元素 - 力扣（LeetCode）
运行代码：
class Solution {
public:
int removeElement(vector<int>& nums, int val) {
int left=0;
int right=0;
while(right<nums.size())
{
if(nums[right]!=val)
{
swap(nums[left],nums[right]);
left++;
}
right++;
}
return left;
}
};1. 双指针初始化
left指针：用于指向当前可以放置非val元素的位置。
right指针：用于遍历数组，寻找非val的元素。2. 遍历数组
使用
while循环遍历数组，right指针从数组的起始位置开始，逐步向右移动。在遍历过程中，
right指针会检查当前元素是否等于val。3. 处理非
val元素
如果
nums[right]不等于val，说明这个元素应该保留在数组中。将这个元素与
nums[left]交换，确保所有非val的元素都集中在数组的左侧。交换后，
left指针向右移动一位，指向下一个可以放置非val元素的位置。4. 处理
val元素
如果
nums[right]等于val，则不做任何操作，right指针继续向右移动，跳过这个元素。5. 返回结果
当
right指针遍历完整个数组后，left指针的位置即为移除所有val元素后数组的新长度。返回
left的值。6. 时间复杂度
该算法的时间复杂度为 O(n)，其中 n 是数组的长度。因为每个元素最多被访问一次。
7. 空间复杂度
该算法的空间复杂度为 O(1)，因为它只使用了常数个额外的变量（
left和right指针）。代码总结
通过双指针技巧，代码高效地将所有非
val元素移动到数组的前部，并返回新数组的长度。这种方法避免了使用额外的空间，直接在原数组上进行操作，是一种原地修改的算法。
示例
假设
nums = [3, 2, 2, 3]，val = 3，代码的执行过程如下：
left = 0,right = 0，nums[0] = 3（等于val），right++。
left = 0,right = 1，nums[1] = 2（不等于val），交换nums[0]和nums[1]，数组变为[2, 3, 2, 3]，left++，right++。
left = 1,right = 2，nums[2] = 2（不等于val），交换nums[1]和nums[2]，数组变为[2, 2, 3, 3]，left++，right++。
left = 2,right = 3，nums[3] = 3（等于val），right++。遍历结束，返回
left = 2，表示新数组的长度为 2，且前两个元素[2, 2]是移除val后的结果。
题二：2460. 对数组执行操作 - 力扣（LeetCode）
基本大体思路：
-
应用特定规则修改数组元素：如果相邻的两个元素相等，则将左边的元素乘以 2，右边的元素置为 0。
-
将所有非零元素移动到数组的前部：保持非零元素的相对顺序，并将所有 0 移动到数组的末尾。
以下是代码的思路解析：
第一部分：应用特定规则修改数组元素
for (int i = 0; i < n - 1; i++) { int left = i, right = i + 1; if (nums[left] == nums[right]) { nums[left] *= 2; nums[right] = 0; } else { continue; } }思路：
遍历数组：
使用一个
for循环遍历数组，从索引0到n-2（因为需要比较当前元素和下一个元素）。定义两个指针
left和right，分别指向当前元素和下一个元素。检查相邻元素是否相等：
如果
nums[left] == nums[right]，则将nums[left]的值乘以 2，并将nums[right]置为 0。如果相邻元素不相等，则跳过，继续遍历。
示例：
假设
nums = [1, 1, 2, 2]：
遍历到
i = 0时，nums[0] == nums[1]，因此nums[0] *= 2（变为 2），nums[1] = 0，数组变为[2, 0, 2, 2]。遍历到
i = 2时，nums[2] == nums[3]，因此nums[2] *= 2（变为 4），nums[3] = 0，数组变为[2, 0, 4, 0]。第二部分：将所有非零元素移动到数组的前部
int dest = -1, cur = 0; while (cur < nums.size()) { if (nums[cur]) { dest++; swap(nums[dest], nums[cur]); cur++; } else { cur++; } }思路：
双指针初始化：
dest指针：用于指向当前可以放置非零元素的位置，初始值为-1。
cur指针：用于遍历数组，初始值为0。遍历数组：
使用
while循环遍历数组，cur指针从0开始，逐步向右移动。处理非零元素：
如果
nums[cur]是非零元素，则将dest指针向右移动一位，并交换nums[dest]和nums[cur]。这样可以将所有非零元素移动到数组的前部，同时保持它们的相对顺序。
处理零元素：
如果
nums[cur]是零元素，则跳过，cur指针继续向右移动。示例：
假设经过第一部分操作后，
nums = [2, 0, 4, 0]：
dest = -1,cur = 0，nums[0] = 2（非零），dest++（变为 0），交换nums[0]和nums[0]（数组不变），cur++。
dest = 0,cur = 1，nums[1] = 0（零），跳过，cur++。
dest = 0,cur = 2，nums[2] = 4（非零），dest++（变为 1），交换nums[1]和nums[2]，数组变为[2, 4, 0, 0]，cur++。
dest = 1,cur = 3，nums[3] = 0（零），跳过，cur++。遍历结束，数组变为
[2, 4, 0, 0]。第三部分：返回结果——返回修改后的数组
nums。总结
时间复杂度：
第一部分遍历数组一次，时间复杂度为 O(n)。
第二部分遍历数组一次，时间复杂度为 O(n)。
总时间复杂度为 O(n)。
空间复杂度：
只使用了常数个额外变量（
dest和cur），空间复杂度为 O(1)。功能：
代码实现了对数组的原地修改，满足题目要求。
示例运行
假设输入
nums = [1, 1, 2, 2]：
第一部分操作后，数组变为
[2, 0, 4, 0]。第二部分操作后，数组变为
[2, 4, 0, 0]。返回
[2, 4, 0, 0]。
二、基于快乐数的举一反三
题一：2460. 对数组执行操作 - 力扣（LeetCode）
运行代码：
class Solution {
public:
bool hasCycle(ListNode *head)
{
ListNode* slow=head;
ListNode* fast=head;
if(head==nullptr||head->next==nullptr)
{
return false;
}
while(fast!=nullptr&&fast->next!=nullptr)
{
slow=slow->next;
fast=fast->next->next;
if(slow==fast)
{
return true;
}
}
return false;
}
};1. 初始化快慢指针
slow是慢指针，每次移动一步。
fast是快指针，每次移动两步。初始时，两个指针都指向链表的头节点
head。2. 处理特殊情况
如果链表为空（
head == nullptr）或只有一个节点（head->next == nullptr），则链表不可能有环，直接返回false。3. 遍历链表
使用
while循环遍历链表，条件是fast != nullptr && fast->next != nullptr。
这个条件确保快指针可以安全地移动两步（避免访问空指针）。
在每次循环中：
慢指针
slow移动一步：slow = slow->next。快指针
fast移动两步：fast = fast->next->next。如果快慢指针相遇（
slow == fast），说明链表中有环，返回true。4. 遍历结束
如果快指针到达链表末尾（
fast == nullptr或fast->next == nullptr），说明链表中没有环，返回false。5. 算法原理
快慢指针的核心思想：
如果链表中有环，快指针最终会追上慢指针（因为快指针每次比慢指针多走一步）。
如果链表中没有环，快指针会先到达链表末尾。
6. 时间复杂度
时间复杂度：O(n)，其中 n 是链表的节点数。
如果链表中无环，快指针会先到达链表末尾，遍历次数为 n/2。
如果链表中有环，快慢指针会在环内相遇，遍历次数小于 n。
空间复杂度：O(1)，只使用了常数个额外空间（两个指针）。
7. 示例
假设链表如下：
初始时，
slow和fast都指向节点 3。移动过程：
slow移动到 2，fast移动到 0。
slow移动到0，fast移动到 2。
slow移动到-4，fast移动到 -4。
slow == fast，说明链表有环，返回true。8. 总结
这段代码通过快慢指针高效地判断链表中是否存在环。
快慢指针算法是解决链表环检测问题的经典方法，具有时间复杂度 O(n) 和空间复杂度 O(1) 的优势。
题二：258. 各位相加 - 力扣（LeetCode）
运行代码：
class Solution {
public:
int addDigits(int num)
{
while(num>=10)
{
int sum=0;
while(num>0)
{
sum+=num%10;
num/=10;
}
num=sum;
}
return num;
}
};1. 外层循环：判断是否需要继续计算
如果
num大于或等于 10，说明num还不是个位数，需要继续计算数位和。如果
num小于 10，说明已经得到结果，直接返回num。2. 内层循环：计算数位和
sum初始化：
每次外层循环开始时，
sum初始化为 0，用于累加num的各个数位。内层循环逻辑：
使用
while (num > 0)循环，逐位取出num的个位数，并累加到sum中。每次取出个位数后，将
num除以 10，去掉已经处理的个位数。更新
num：
内层循环结束后，将
sum赋值给num，继续外层循环的判断。3. 返回结果
当
num小于 10 时，跳出外层循环，返回num，即为最终的结果。4. 示例
假设输入
num = 38，代码的执行过程如下：
第一次外层循环：
num = 38（大于等于 10），进入内层循环。内层循环：
sum += 8（38 % 10），sum = 8，num = 3（38 / 10）。
sum += 3（3 % 10），sum = 11，num = 0（3 / 10）。内层循环结束，
num = sum = 11。第二次外层循环：
num = 11（大于等于 10），进入内层循环。内层循环：
sum += 1（11 % 10），sum = 1，num = 1（11 / 10）。
sum += 1（1 % 10），sum = 2，num = 0（1 / 10）。内层循环结束，
num = sum = 2。外层循环结束：
num = 2（小于 10），跳出循环，返回2。5. 时间复杂度
时间复杂度：O(log n)，其中 n 是输入的数字。
每次外层循环会将
num减少到其数位和，数位和的规模远小于num。内层循环的次数取决于
num的位数，每次内层循环的时间复杂度为 O(log n)。空间复杂度：O(1)，只使用了常数个额外变量。
题三： 263. 丑数 - 力扣（LeetCode）
运行代码：
class Solution {
public:
bool isUgly(int n)
{
int arr[]={2,3,5};
if(n<=0)
{
return false;
}
else
{
for(int i=0;i<3;i++)
{
while(n%arr[i]==0)
{
n/=arr[i];
}
}
return n==1;
}
}
};1. 处理特殊情况
如果
n小于或等于 0，直接返回false，因为丑数必须是正整数。2. 定义质因数数组
定义一个数组
arr，包含 2、3、5 这三个质因数。3. 循环去除质因数
使用一个
for循环遍历数组arr中的每个质因数。对于每个质因数，使用
while循环不断将n除以该质因数，直到n不再能被该质因数整除为止。这样做的目的是将
n中的所有 2、3、5 的质因数全部去除。4. 判断最终结果
如果
n最终变为 1，说明n只包含 2、3、5 这些质因数，因此n是丑数，返回true。如果
n最终不为 1，说明n包含其他质因数，因此n不是丑数，返回false。总结
该算法通过不断去除
n中的 2、3、5 质因数，最终判断n是否变为 1 来判断n是否为丑数。时间复杂度为 O(log n)，因为每次除法操作都会减少
n的大小。空间复杂度为 O(1)，只使用了常数级别的额外空间。
题四：1945. 字符串转化后的各位数字之和 - 力扣（LeetCode）
运行代码:
class Solution {
public:
int getLucky(string s, int k)
{
string digits;
for(auto ch : s)
{
// 将字符转换为对应的数字并追加到digits字符串中
digits += to_string(ch - 'a' + 1);
}
for(int i = 1; i <= k && digits.size() > 1; ++i)
{
int sum = 0;
for(auto ch : digits)
{
// 将字符转换为数字并累加
sum += stoi(string(1, ch));
}
// 将累加结果转换为字符串
digits = to_string(sum);
}
// 返回最终结果
return stoi(digits);
}
};问题分析
输入：
一个字符串
s，由小写字母组成。一个整数
k，表示需要进行“数字求和”操作的次数。转换规则：
将字符串中的每个字母转换为其在字母表中的位置值（
a -> 1,b -> 2, ...,z -> 26）。将这些位置值拼接成一个数字字符串。
操作规则：
对数字字符串中的每一位数字求和，得到一个新的数字。
重复上述操作
k次，或者直到数字字符串的长度变为 1（即无法继续求和）。输出：
最终的数字结果。
代码思路
第一步：字母转换为数字字符串
遍历字符串
s中的每个字符ch。将字符
ch转换为对应的数字：
公式：
ch - 'a' + 1。
ch - 'a'得到字符ch在字母表中的偏移量（a -> 0,b -> 1, ...,z -> 25）。
+ 1将其转换为位置值（a -> 1,b -> 2, ...,z -> 26）。将数字转换为字符串并追加到
digits中。示例：
输入
s = "abc"：
a -> 1,b -> 2,c -> 3。
digits = "123"。第二步：数字求和操作
进行
k次求和操作：
每次操作中，遍历
digits中的每个字符（即数字的每一位）。将字符转换为数字并累加到
sum中。将
sum转换为字符串，更新digits。如果
digits的长度变为 1，则提前结束循环（因为无法继续求和）。示例：
输入
digits = "123",k = 2：
第一次操作：
sum = 1 + 2 + 3 = 6。
digits = "6"。第二次操作：
由于
digits的长度已经是 1，循环结束。第三步：返回结果
将最终的
digits转换为整数并返回。示例：
最终
digits = "6"，返回6。代码实现的关键点
字符到数字的转换：
使用
ch - 'a' + 1将字母转换为对应的数字。使用
to_string将数字转换为字符串。数字求和：
使用
stoi(string(1, ch))将字符转换为数字。使用
to_string(sum)将求和结果转换回字符串。循环控制：
最多进行
k次操作。如果
digits的长度变为 1，提前结束循环。步骤：
字母转换为数字字符串：
l -> 12,e -> 5,e -> 5,t -> 20,c -> 3,o -> 15,d -> 4,e -> 5。
digits = "12552031545"。第一次求和操作：
sum = 1 + 2 + 5 + 5 + 2 + 0 + 3 + 1 + 5 + 4 + 5 = 33。
digits = "33"。第二次求和操作：
sum = 3 + 3 = 6。
digits = "6"。返回结果：
6。时间复杂度分析
字母转换：
遍历字符串
s，时间复杂度为O(n)，其中n是字符串的长度。数字求和操作：
每次求和操作需要遍历
digits的所有字符。最多进行
k次操作。最坏情况下，
digits的长度可能很大，但每次求和操作会显著减少其长度。总体时间复杂度为
O(k * m)，其中m是digits的最大长度。
题五：2457. 美丽整数的最小增量 - 力扣（LeetCode）
思路：
- 得到当前数字的各位数字之和，如果<=target就直接返回0
- 当前值各位数之和大于了target，那么考虑进行进位，当前数大于，那么个位的数字往上变大更不可能满足条件
- 寻找最小值，末尾为0则最小 所以我们令此时的个位为0，十位进1，同理，如果计算后仍旧大于target，我们将十位变为0，百位进1
- 举例子:123 3
- 123 和为6>3，那么124-129的各位数和不可能小于6,直到进位后130达到4才小于123的6
- 130 和为4>3 那么131-139也不可能小于4，也只有进位后200才小于130的4
- 200 和为2<3，所以200-123的差就是最小增量
运行代码：
class Solution {
public:
int sub(long long n)//位数求和
{
int sum = 0;
while (n > 0)
{
sum += n % 10;
n /= 10;
}
return sum;
}
long long makeIntegerBeautiful(long long n, int target)
{
if (sub(n) <= target)
return 0;
long long i = 10;
long long t=n;//保存原值
while (sub(n) > target)
{
n=n/i;//去掉当前末位(即末位变为0) 第一轮123-> 12 第二轮130->1
n++;//进位 第一轮12+1->13 第二轮1+1->2
n*=i;//末尾变为0 第一轮13*10->130 第二轮2*100->200
i*=10;//每一次进位
}
return n-t;
}
};题六：2507. 使用质因数之和替换后可以取到的最小值 - 力扣（LeetCode）
运行代码：
class Solution {
public:
// 辅助函数：计算 n 的质因数之和
int sumOfPrimeFactors(int n) {
int sum = 0;
// 从最小的质数 2 开始分解
for (int i = 2; i * i <= n; i++) {
while (n % i == 0) {
sum += i; // 累加质因数
n /= i;
}
}
// 如果 n 仍然是大于 1 的质数
if (n > 1) {
sum += n;
}
return sum;
}
// 主函数：计算 n 的最小值
int smallestValue(int n) {
while (true) {
int sum = sumOfPrimeFactors(n); // 计算质因数之和
if (sum == n) { // 如果 n 已经是质数
break;
}
n = sum; // 替换 n 为质因数之和
}
return n;
}
};问题分析
输入：
一个正整数
n。操作规则：
将
n替换为其质因数之和。重复上述操作，直到
n无法再被分解（即n是一个质数）。输出：
最终
n的最小值（即一个质数）。代码思路
第一步：质因数分解
对于一个正整数
n，找到其所有质因数。如果
n能被某个质因数多次整除，则在求和时，该质因数需要被累加多次。第二步：替换为质因数之和
将
n替换为其质因数之和。重复上述操作，直到
n是一个质数。第三步：返回结果
最终
n的值即为所求的最小值。代码实现的关键点
1.
sumOfPrimeFactors函数
功能：计算整数
n的所有质因数之和。实现：
从最小的质数
2开始，逐个检查是否能整除n。如果能整除，则将该质因数累加到
sum中，并将n除以该质因数。重复上述过程，直到
n变为1或无法再被分解。如果
n仍然是大于1的质数，则将其累加到sum中。2.
smallestValue函数
功能：将
n替换为其质因数之和，直到n变为质数。实现：
循环调用
sumOfPrimeFactors，计算n的质因数之和。如果
sum == n，说明n已经是质数，退出循环。否则，将
n替换为sum，继续循环。示例运行
步骤：
第一次分解：
质因数分解：
12 = 2 * 2 * 3。质因数之和：
2 + 2 + 3 = 7。替换
n为7。第二次分解：
7是质数，无法再分解。返回
7。时间复杂度分析
质因数分解：
每次分解的时间复杂度为
O(sqrt(n))。循环次数：
每次替换
n为质因数之和，n的值会显著减小。最坏情况下，循环次数为
O(log n)次。总体时间复杂度：
O(sqrt(n) * log n)。
题七：2520. 统计能整除数字的位数 - 力扣（LeetCode）
运行代码：
class Solution {
public:
int countDigits(int num)
{
int t = num, res = 0;
while (t)
{
if (num % (t % 10) == 0)
{
res += 1;
}
t /= 10;
}
return res;
}
};问题分析
输入：
一个整数
num。目标：
计算
num中有多少位数字能够整除num本身。关键点：
需要逐位提取
num的数字。判断每一位数字是否能整除
num。代码思路
第一步：初始化
使用变量
t保存num的值，避免直接修改num。使用变量
res记录满足条件的数字个数，初始值为0。第二步：逐位提取数字
使用
while循环遍历t的每一位数字：
t % 10：获取t的最后一位数字。
t /= 10：去掉t的最后一位数字。对每一位数字进行判断：
如果
num % (t % 10) == 0，说明当前数字能整除num。将
res的值加1。第三步：返回结果
循环结束后，
res中存储的就是满足条件的数字个数。返回
res。代码实现的关键点
1. 逐位提取数字
使用
t % 10获取当前位的数字。使用
t /= 10去掉当前位的数字。2. 判断是否能整除
使用
num % (t % 10) == 0判断当前数字是否能整除num。3. 边界条件
如果
num的某一位是0，则需要跳过，因为除数不能为0。
在这段代码中，如果
t % 10 == 0，num % 0会导致运行时错误。因此，代码假设num不包含0。示例运行
步骤：
初始化：
t = 1248，res = 0。第一次循环：
t % 10 = 8。
1248 % 8 == 0，满足条件。
res = 1。
t = 1248 / 10 = 124。第二次循环：
t % 10 = 4。
1248 % 4 == 0，满足条件。
res = 2。
t = 124 / 10 = 12。第三次循环：
t % 10 = 2。
1248 % 2 == 0，满足条件。
res = 3。
t = 12 / 10 = 1。第四次循环：
t % 10 = 1。
1248 % 1 == 0，满足条件。
res = 4。
t = 1 / 10 = 0。循环结束，返回
res = 4。时间复杂度分析
循环次数：
while循环的次数等于num的位数，即O(log num)。总体时间复杂度：
O(log num)。