C++ LeetCode 算法基础：位运算、摩尔投票与双指针实战

一、只出现一次的数字：位运算应用

在数组中，若除某个元素仅出现一次外，其余每个元素均出现两次，我们需要找出这个单一出现的元素。直接遍历查找的时间复杂度为 $O(n^2)$，而利用位运算中的异或（XOR）特性，可以将时间复杂度优化至 $O(n)$，空间复杂度降至 $O(1).

核心原理：

• 归零律：任何数与自身异或结果为 0（$a \oplus a = 0$）。
• 恒等律：任何数与 0 异或结果为其本身（$a \oplus 0 = a$）。
• 交换律与结合律：异或运算的顺序不影响最终结果。

因此，将所有数字依次异或，成对出现的数字会相互抵消为 0，最终剩下的即为唯一的那个数字。例如在数组 [4, 1, 2, 1, 2] 中：

1. $4 \oplus 1 = 5$
2. $5 \oplus 2 = 7$
3. $7 \oplus 1 = 6$ （此时两个 1 已抵消）
4. $6 \oplus 2 = 4$ （此时两个 2 已抵消）
5. 最终结果为 4。

C++ 实现：

int singleNumber(vector<int>& nums) {
    int res = 0;
    for (int num : nums) {
        res ^= num;
    }
    return res;
}

二、多数元素：摩尔投票法

多数元素是指在数组中出现次数超过 n/2 的元素。虽然排序后返回中间值即可解决问题，但时间复杂度高达 $O(n \log n)$。摩尔投票法（Moore Voting Algorithm），也称为“同归于尽”法，能够在线性时间 $O(n)$ 和常数空间 $O(1)$ 内找到该元素。

第 1 步：初始化计数器与候选人

定义一个计数变量 count 初始化为 1，并设定第一个数组元素 res 为当前候选的多数元素。

第 2 步：遍历数组进行投票对抗

从第二个元素开始遍历，逻辑如下：

• 若当前元素等于候选人 res，则 count++（支持票增加）。
• 若当前元素不等于 res，则 count--（反对票增加，相当于两人同归于尽）。
• 当 count 降为 0 时，说明之前的候选人及其支持者已完全抵消，更新新的候选人为当前元素 nums[i]，并重置 count = 1。

代码实现：

int majorityElement(vector<int>& nums) {
    // 摩尔投票法：同归于尽
    int count = 1;
    int res = nums[0];
    
    for (size_t i = 1; i < nums.size(); ++i) {
        if (res == nums[i]) {
            count++;
        } else {
            count--;
            if (count == 0) {
                res = nums[i];
                count = 1;
            }
        }
    }
    return res;
}

三、三数之和：排序与双指针

三数之和（3Sum）要求找出数组中所有和为 0 的不重复三元组。此题难度在于处理重复元素与高效搜索。最佳策略是先排序，再使用双指针。

核心思路

1. 排序：对数组进行升序排序，便于去重和移动指针。
2. 固定首位：遍历数组，固定第一个数 nums[i]。
3. 双指针夹逼：定义左指针 left = i + 1，右指针 right = nums.size() - 1。
4. 求和调整：
   • 若 nums[i] + nums[left] + nums[right] == 0，记录结果，并向内收缩两端指针。
   • 若和大于 0，说明数值过大，右指针左移（right--）。
   • 若和小于 0，说明数值过小，左指针右移（left++）。

关键去重技巧

• 跳过重复的首位：若 i > 0 且 nums[i] == nums[i-1]，则跳过当前迭代，避免生成重复三元组。
• 跳过重复的双指针：在找到目标组合后，在收缩指针前，需跳过与当前指针位置值相同的后续元素。
• 提前终止：若 nums[i] > 0，由于数组已排序，后续所有元素均为正数，不可能凑成和为 0，可直接跳出循环。

C++ 实现：

vector<vector<int>> threeSum(vector<int>& nums) {
    vector<vector<int>> result;
    sort(nums.begin(), nums.end());
    
    for (size_t i = 0; i < nums.size() - 2; ++i) {
        // 剪枝：第一个数大于0，后续不可能为0
        if (nums[i] > 0) break;
        
        // 去重：跳过相同的首位元素
        if (i > 0 && nums[i] == nums[i - 1]) continue;
        
        int left = i + 1;
        int right = nums.size() - 1;
        int target = -nums[i];
        
        while (left < right) {
            int sum = nums[left] + nums[right];
            
            if (sum == target) {
                result.push_back({nums[i], nums[left], nums[right]});
                
                // 去重：左指针跳过相同值
                while (left < right && nums[left] == nums[left + 1]) left++;
                // 去重：右指针跳过相同值
                while (left < right && nums[right] == nums[right - 1]) right--;
                
                left++;
                right--;
            } else if (sum < target) {
                left++;
            } else {
                right--;
            }
        }
    }
    return result;
}

注意：

1. Arrays.asList() 在 Java 中常用，但在 C++ 标准库中，直接使用初始化列表 {val1, val2, val3} 或构造函数更高效。
2. 务必确保在处理完一组解后，左右指针都向内侧移动一位，否则可能导致死循环或遗漏新组合。
3. 预处理排序是双指针法的前提，不可省略。

以上就是 C++ LeetCode 算法基础：位运算、摩尔投票与双指针实战的详细内容，更多关于 C++ 数据结构与算法技巧的资料请关注本站其它相关文章！