LeetCode 2576题解：双指针法求解最多标记下标（排序+贪心策略）
一、题目解读
LeetCode 2576题要求在一个整数数组中寻找最多可标记的下标对：若 nums[i] * 2 <= nums[j]（i ≠ j），则下标 i 和 j 可配对标记。例如，输入 [3,1,2,4,5]，可标记 (0,3) 和 (2,4)，输出最多标记对数为 2。题目难点在于如何在无序数组中高效找到符合条件的配对，并最大化配对数量。
二、解题思路
1. 排序预处理：对原数组 nums 进行升序排序，确保相同元素聚集，便于后续配对。
2. 双指针划分：将排序后的数组分为左右两半（左指针 left=0，右指针 right=n/2），从中间向两端扩展寻找配对。
3. 贪心匹配：若 2 * nums[left] <= nums[right]，则 left 与 right 可配对，同时双指针向内收缩（left++, right++）；否则仅右指针右移，寻找更大 nums[right]。
4. 计数优化：每次配对成功计数加2，最终返回总配对数。
三、解题步骤
1. 排序数组：调用 sort(nums.begin(), nums.end()) 将 nums 升序排列。
2. 初始化指针：
○ left=0（左半区起始），right=n/2（右半区起始）。
3. 循环匹配，当 left < n/2 且 right < n 时：
若 2 * nums[left] <= nums[right]，说明 left 与 right 可配对，计数 count += 2，双指针向内移动（left++, right++）。
否则（nums[left] * 2 > nums[right]），仅右指针右移（right++），尝试更大数值配对。
4. 返回结果：最终 count 即为最多可标记的下标对数。
四、代码及注释
class Solution {
public:
int maxNumOfMarkedIndices(vector<int>& nums) {
sort(nums.begin(), nums.end()); // 先对数组排序，便于后续双指针匹配
int n = nums.size();
int left = 0, right = n / 2; // 左右指针初始化（左从0开始，右从中间开始）
int count = 0; // 标记对数量
while (left < n / 2 && right < n) { // 循环条件：左右指针均未越界
if (2 * nums[left] <= nums[right]) { // 若满足配对条件
count += 2; // 计数+2，标记一对
left++; // 左指针右移（寻找下一可配对元素）
right++; // 右指针右移（因排序后右半区递增，需尝试更大值）
} else { // 若不满足条件
right++; // 仅右指针右移，跳过当前left与right的组合
}
}
return count; // 返回最终标记对数
}
};五、总结
本解法通过排序将无序问题转化为有序区间配对，结合双指针法实现高效贪心匹配，时间复杂度为 O(nlogn)（排序）+ O(n)（双指针遍历），空间复杂度为 O(1)（原地排序）。关键点包括：
1. 排序预处理：确保元素有序，降低后续匹配复杂度。
2. 双指针贪心策略：通过固定左指针、移动右指针寻找配对，避免暴力枚举。
3. 边界判断优化：利用排序后的递增特性，不满足条件时直接右移指针，减少无效比较。
该算法兼顾效率与简洁性，是解决此类区间匹配问题的典型优化思路，适用于需要最大化配对数的场景。
原创内容 转载请注明出处
