LeetCode 2576题解：双指针法求解最多标记下标（排序+贪心策略）

一、题目解读

LeetCode 2576题要求在一个整数数组中寻找最多可标记的下标对：若 nums[i] * 2 <= nums[j]（i ≠ j），则下标 i 和 j 可配对标记。例如，输入 [3,1,2,4,5]，可标记 (0,3) 和 (2,4)，输出最多标记对数为 2。题目难点在于如何在无序数组中高效找到符合条件的配对，并最大化配对数量。

二、解题思路

采用“排序+双指针法+贪心策略”的组合思路：

排序预处理：对原数组 nums 进行升序排序，确保相同元素聚集，便于后续配对。
双指针划分：将排序后的数组分为左右两半（左指针 left=0，右指针 right=n/2），从中间向两端扩展寻找配对。
贪心匹配：若 2 * nums[left] <= nums[right]，则 left 与 right 可配对，同时双指针向内收缩（left++, right++）；否则仅右指针右移，寻找更大 nums[right]。
计数优化：每次配对成功计数加2，最终返回总配对数。

三、解题步骤

排序数组：调用 sort(nums.begin(), nums.end()) 将 nums 升序排列。
初始化指针：

○ left=0（左半区起始），right=n/2（右半区起始）。

循环匹配，当 left < n/2 且 right < n 时：

若 2 * nums[left] <= nums[right]，说明 left 与 right 可配对，计数 count += 2，双指针向内移动（left++, right++）。

否则（nums[left] * 2 > nums[right]），仅右指针右移（right++），尝试更大数值配对。
返回结果：最终 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;                      // 返回最终标记对数
    }
};