探索算法系列 - 双指针
目录
移动零（原题链接）
给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
请注意 ，必须在不复制数组的情况下原地对数组进行操作。
解题思路
- 定义两个指针
cur和dest。cur用于遍历整个数组。dest指向下一个非零元素应该放置的位置。- 初始化
dest为-1，这是因为我们需要在第一次找到非零元素时将其值赋给dest并且增加dest的值。
步骤说明
初始化：
cur从0开始。dest从-1开始（表示还没有遇到非零元素）。遍历数组：
- 使用循环遍历整个数组
nums。- 对于数组中的每一个元素
nums[cur]，检查它是否是非零元素。
- 如果
nums[cur]不为0，则执行以下操作：
- 将
dest加1。- 交换
nums[dest]和nums[cur]的值。结束条件：
- 当
cur遍历完整个数组后，循环结束。结果：
- 所有的非零元素都已经被移动到了数组的前半部分，并保持了原有的顺序。
- 所有的0元素都被移动到了数组的后半部分。
具体代码
class Solution { public: void moveZeroes(vector<int>& nums) { for (int cur = 0, dest = -1; cur < nums.size(); cur++) { if (nums[cur]) { swap(nums[++dest], nums[cur]); } } } };
复写零（原题链接）
给你一个长度固定的整数数组 arr ，请你将该数组中出现的每个零都复写一遍，并将其余的元素向右平移。
注意：请不要在超过该数组长度的位置写入元素。请对输入的数组 就地 进行上述修改，不要从函数返回任何东西。
解题思路
初始化变量
预处理：
复制与调整
步骤说明
初始化：
cur从0开始。dest从-1开始。n是数组的长度。预处理：
- 使用循环遍历整个数组
arr。- 如果
arr[cur]是0，则dest增加2；否则，dest增加1。- 如果
dest大于等于n-1，则退出循环。特殊情况处理：
- 如果
dest等于n，说明最后一个位置应该是一个复制的0元素，需要将最后一个元素设置为0，并减少dest的值以确保不会超出数组长度。- 减少
cur的值以便在接下来的步骤中重新处理这个位置。复制与调整：
- 从
cur开始向左遍历数组。- 如果
arr[cur]不为0，则直接将arr[cur]复制到dest的位置。- 如果
arr[cur]为0，则需要复制两次0元素到dest的位置。- 在每一步之后减少
dest的值，并且每次循环结束后减少cur的值。结束条件：
- 当
cur小于0 时，循环结束。
具体代码
class Solution { public: void duplicateZeros(vector<int>& arr) { int cur = 0, dest = -1, n = arr.size(); while (cur < n) { if (arr[cur]) dest++; else dest += 2; if (dest >= n - 1) break; cur++; } if (dest == n) { arr[n - 1] = 0; cur--; dest -= 2; } while (cur >= 0) { if (arr[cur]) arr[dest--] = arr[cur--]; else { arr[dest--] = 0; arr[dest--] = 0; cur--; } } } };
快乐数（原题链接）
编写一个算法来判断一个数 n 是不是快乐数。
「快乐数」 定义为：
- 对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。
- 然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。
- 如果这个过程 结果为 1，那么这个数就是快乐数。
如果 n 是 快乐数 就返回 true ；不是，则返回 false 。
首先我们先证明：
对于任意正整数，通过上述过程要么最终变为 1，要么进入一个循环，而不会出现其他情况。（鸽巢原理）
证明过程
有限性：
- 假设初始数为 𝑛n，且 𝑛n 有 𝑑d 位数字。
- 每次迭代产生的新数的最大值是 𝑑×81d×81，这是因为每一位上的数字最大是 9，而 92=8192=81。
- 因此，无论初始数有多大，经过若干次迭代后，得到的数将不会超过 𝑑×81d×81。
循环检测：
- 既然每次迭代产生的数都是有限集合内的一个数，那么随着迭代次数的增加，必然会出现重复的数。
- 当重复出现时，就会形成一个循环，因为一旦出现了一个数，之后的迭代结果将完全由之前的数决定，形成一个闭环。
唯一循环：
- 如果一个数 𝑛n 通过上述过程变成了 1，那么它就是一个快乐数。
- 如果一个数进入了循环，而循环中没有 1，那么这个数就是一个不快乐数。
- 除了 1 之外，所有可能的循环都是有限的，因为生成的数总是有限集合内的一个数。
解题思路
- 定义辅助函数
bitSum：计算一个数各位数字的平方和。- 使用快慢指针法
isHappy：通过快慢指针法检测循环，判断是否为快乐数。
步骤说明
- 初始化变量
slow和fast：
slow初始化为n。fast初始化为bitSum(n)，即对n应用一次bitSum函数的结果。- 使用快慢指针法检测循环：
- 在
slow和fast不相等的情况下，继续执行循环。- 在每次循环中：
- 更新
slow为bitSum(slow)，即对slow应用一次bitSum函数。- 更新
fast为bitSum(bitSum(fast))，即对fast应用两次bitSum函数。- 判断是否为快乐数：
- 如果
slow和fast最终相等，并且等于 1，则n是快乐数。- 如果
slow和fast最终相等但不等于 1，则n不是快乐数，因为它进入了循环。
具体代码
class Solution { public: int bitSum(int n) { int sum = 0; while(n) { int t = n % 10; sum += t * t; n /= 10; } return sum; } bool isHappy(int n) { int slow = n,fast = bitSum(n); while(slow != fast) { slow = bitSum(slow); fast = bitSum(bitSum(fast)); } return slow == 1; } };
盛最多水的容器（原题链接）
给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。
找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
返回容器可以储存的最大水量。
说明：你不能倾斜容器。
解题思路
- 双指针法：使用两个指针
left和right，分别指向数组的起始位置和结束位置。- 计算面积：每次计算由
left和right指向的两条线形成的容器面积。- 更新最大面积：记录每次计算的最大面积。
- 移动指针：根据高度较小的一侧来移动指针，以寻找可能更大的面积。
步骤说明
- 初始化变量
left和right分别指向数组的首尾，ret用于记录最大的面积。- 循环条件：当
left小于right时，继续执行循环。- 计算面积：
- 计算当前容器的面积
v，面积由较短边的高度和两线间的距离决定：v = min(height[left], height[right]) * (right - left)。- 更新
ret为当前面积v和已记录的最大面积ret中较大的那个值。- 移动指针：
- 如果
height[left]小于height[right]，则将left向右移动一位。- 否则，将
right向左移动一位。- 循环结束：当
left不再小于right时，循环结束。- 返回结果
ret。
具体代码
class Solution { public: int maxArea(vector<int>& height) { int left = 0, right = height.size() - 1, ret = 0; while(left < right) { int v = min(height[left], height[right]) * (right - left); ret = max(ret, v); if(height[left] < height[right]) left++; else right--; } return ret; } };
有效三角形的个数（原题链接）
给定一个包含非负整数的数组 nums ，返回其中可以组成三角形三条边的三元组个数。
解题思路
- 排序：首先对数组进行排序。
- 双指针法：使用两个指针
left和right，分别指向数组的起始位置和当前遍历位置的前一个位置。- 遍历：从数组的末尾开始遍历，每次选取一个数作为最长边。
- 条件判断：根据构成三角形的条件，移动
left和right指针来寻找所有可能的组合。
步骤说明
排序:
- 使用
sort函数对输入数组nums进行升序排序。初始化变量:
ret用于记录满足条件的组合数量。n是数组的长度。遍历数组:
- 从数组的末尾开始，即从最长的边开始遍历。
- 使用循环变量
i从n - 1开始递减到2（因为至少需要三个数才能构成三角形）。双指针法:
- 在每次循环中，使用两个指针
left和right，分别初始化为 0 和i - 1。- 使用内部循环，当
left小于right时，继续执行循环。- 根据构成三角形的条件（两边之和大于第三边），进行如下操作：
- 如果
nums[left] + nums[right] > nums[i]，则满足条件，此时所有位于left和right之间的数都可以与nums[left]和nums[i]构成三角形，因此加上right - left的数量。- 如果不满足条件，则将
left向右移动一位，尝试更大的数。- 如果满足条件，则将
right向左移动一位，尝试较小的数。返回结果:
- 返回
ret，即满足条件的组合数量。
具体代码
class Solution { public: int triangleNumber(vector<int>& nums) { sort(nums.begin(), nums.end()); int ret = 0, n = nums.size(); for(int i = n - 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; } };
查找总价格为目标值的两个商品（原题链接）
购物车内的商品价格按照升序记录于数组 price。请在购物车中找到两个商品的价格总和刚好是 target。若存在多种情况，返回任一结果即可。
解题思路
- 双指针法：使用两个指针
left和right，分别指向数组的起始位置和结束位置。- 计算和：每次计算由
left和right指向的两个数的和。- 更新指针：根据和与目标值的关系来更新指针。
- 返回结果：如果找到了符合条件的两个数，则返回这两个数；否则，返回
{ -1, -1 }。
步骤说明
- 初始化变量
left和right分别指向数组的首尾。- 循环条件：当
left小于right时，继续执行循环。- 计算和：
- 计算当前和
sum：sum = price[left] + price[right]。- 更新指针：
- 如果
sum大于target，则将right向左移动一位。- 如果
sum小于target，则将left向右移动一位。- 如果
sum等于target，则找到了符合条件的两个数，返回这两个数。- 循环结束：当
left不再小于right时，循环结束。- 返回结果：如果没有找到符合条件的两个数，则返回
{ -1, -1 }。
具体代码
class Solution { public: vector<int> twoSum(vector<int>& price, int target) { int left = 0, right = price.size() - 1; while(left < right) { int sum = price[left] + price[right]; if(sum > target) right--; else if(sum < target) left++; else return {price[left], price[right]}; } return {-1,-1}; } };
三数之和（原题链接）
给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。
解题思路
- 排序：首先对数组进行排序。
- 双指针法：使用两个指针
left和right，分别指向数组的当前位置的后一个位置和数组的末尾。- 遍历：从数组的开头开始遍历，每次选取一个数作为第一个数。
- 条件判断：根据和为 0 的条件，移动
left和right指针来寻找所有可能的组合。- 去重：在遍历过程中，跳过重复的元素以避免重复的组合。
步骤说明
排序:
- 使用
sort函数对输入数组nums进行升序排序。初始化变量:
ret用于记录满足条件的组合。n是数组的长度。遍历数组:
- 从数组的开头开始遍历，使用循环变量
i。- 当
nums[i]大于 0 时，提前结束遍历（因为之后的组合肯定大于 0）。双指针法:
- 在每次循环中，使用两个指针
left和right，分别初始化为i + 1和n - 1。- 使用内部循环，当
left小于right时，继续执行循环。- 计算和
sum：sum = nums[left] + nums[right]。- 根据和与目标值 0 的关系，进行如下操作：
- 如果
sum大于 0，则将right向左移动一位。- 如果
sum小于 0，则将left向右移动一位。- 如果
sum等于 0，则将当前组合加入到结果中，并移动指针以寻找下一个可能的组合。- 在找到有效的组合后，需要跳过重复的元素，以避免重复的组合。
返回结果:
- 返回
ret，即满足条件的组合列表。
具体代码
class Solution { public: vector<vector<int>> threeSum(vector<int>& nums) { vector<vector<int>> ret; sort(nums.begin(), nums.end()); int n = nums.size(); for (int i = 0; i < n; ) { if (nums[i] > 0) break; int left = i + 1, right = n - 1, target = -nums[i]; while (left < right) { int sum = nums[left] + nums[right]; if (sum > target) right--; else if (sum < target) left++; else { ret.push_back({ nums[i], nums[right], nums[left] }); left++, right--; while (left < right && nums[left] == nums[left - 1]) left++; while (left < right && nums[right] == nums[right + 1]) right--; } } i++; while (i < n && nums[i] == nums[i - 1]) i++; } return ret; } };
四数之和（原题链接）
给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。
请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] （若两个四元组元素一一对应，则认为两个四元组重复）：
0 <= a, b, c, d < na、b、c和d互不相同nums[a] + nums[b] + nums[c] + nums[d] == target
你可以按 任意顺序 返回答案 。
解题思路
- 排序：首先对数组进行排序。
- 双指针法：使用两个指针
left和right，分别指向数组的当前位置的后一个位置和数组的末尾。- 嵌套循环：使用两层嵌套循环，外层循环遍历数组中的两个数，内层使用双指针法寻找另外两个数，使得四数之和等于目标值。
- 去重：在遍历过程中，跳过重复的元素以避免重复的组合。
步骤说明
排序:
- 使用
sort函数对输入数组nums进行升序排序。初始化变量:
ret用于记录满足条件的组合。n是数组的长度。外层循环:
- 从数组的开头开始遍历，使用循环变量
i。- 内层循环遍历数组中的第二个数，使用循环变量
j。双指针法:
- 在每次内外层循环中，使用两个指针
left和right，分别初始化为j + 1和n - 1。- 使用内部循环，当
left小于right时，继续执行循环。- 计算和
sum：sum = nums[left] + nums[right]。- 根据和与目标值
target的关系，进行如下操作：
- 如果
sum小于target - nums[i] - nums[j]，则将left向右移动一位。- 如果
sum大于target - nums[i] - nums[j]，则将right向左移动一位。- 如果
sum等于target - nums[i] - nums[j]，则将当前组合加入到结果中，并移动指针以寻找下一个可能的组合。- 在找到有效的组合后，需要跳过重复的元素，以避免重复的组合。
返回结果:
- 返回
ret，即满足条件的组合列表。
具体代码
class Solution { public: vector<vector<int>> fourSum(vector<int>& nums, int target) { vector<vector<int>> ret; sort(nums.begin(), nums.end()); int n = nums.size(); for(int i = 0; i < n; ) { for(int j = i + 1; j < n; ) { int left = j + 1, right = n - 1; long long aim = (long long)target - nums[i] - nums[j]; while(left < right) { int sum = nums[left] + nums[right]; if(sum < aim) left++; else if(sum > aim) right--; else { ret.push_back({nums[i], nums[j], nums[left], nums[right]}); left++, right--; while (left < right && nums[left] == nums[left - 1]) left++; while (left < right && nums[right] == nums[right + 1]) right--; } } j++; while(j < n && nums[j] == nums[j-1]) j++; } i++; while(i < n && nums[i] == nums[i - 1]) i++; } return ret; } };
原文地址：https://blog.csdn.net/weixin_66330442/article/details/140680682
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！