数组技巧（多数元素 · 缺失数字 · 除自身之外的乘积）

多数元素（LeetCode 169）

Boyer-Moore 投票算法：相互抵消，最后剩的就是多数元素。

int majorityElement(int[] nums) {
    int count = 0, candidate = 0;
    for (int n : nums) {
        if (count == 0) candidate = n;
        count += (n == candidate) ? 1 : -1;
    }
    return candidate;
}

O(n) 时间，O(1) 空间，无需验证（题目保证存在多数元素）。

多数元素 II（LeetCode 229）：找出所有出现次数 > n/3 的元素（最多两个），用两个候选数做投票。

缺失数字（LeetCode 268）

数组包含 [0, n] 中除某个数外的所有整数：

数学法（高斯求和）：

int missingNumber(int[] nums) {
    int n = nums.length;
    int expected = n * (n + 1) / 2;
    int actual = 0;
    for (int num : nums) actual += num;
    return expected - actual;
}

位运算法（异或）：

int missingNumberXor(int[] nums) {
    int result = nums.length;
    for (int i = 0; i < nums.length; i++)
        result ^= i ^ nums[i];  // 相同数字异或抵消
    return result;
}

除自身以外数组的乘积（LeetCode 238）

不能用除法，O(n) 时间，O(1) 额外空间（输出数组不算）：

int[] productExceptSelf(int[] nums) {
    int n = nums.length;
    int[] result = new int[n];

    // 1. 左侧所有元素的乘积
    result[0] = 1;
    for (int i = 1; i < n; i++) result[i] = result[i - 1] * nums[i - 1];

    // 2. 右侧所有元素的乘积（从右向左，复用 result 数组）
    int right = 1;
    for (int i = n - 1; i >= 0; i--) {
        result[i] *= right;
        right *= nums[i];
    }
    return result;
}

思路：result[i] = 左侧乘积 × 右侧乘积，两次扫描分别积累。

找到所有数组中消失的数字（LeetCode 448）

List<Integer> findDisappearedNumbers(int[] nums) {
    // 将出现过的数字对应索引处的值取负（标记）
    for (int num : nums) {
        int idx = Math.abs(num) - 1;
        if (nums[idx] > 0) nums[idx] *= -1;
    }
    List<Integer> result = new ArrayList<>();
    for (int i = 0; i < nums.length; i++) {
        if (nums[i] > 0) result.add(i + 1);
    }
    return result;
}

寻找重复数（LeetCode 287）

数组 [1, n] 含一个重复数，O(n) 时间 O(1) 空间： 快慢指针（把数组看成链表）

int findDuplicate(int[] nums) {
    int slow = nums[0], fast = nums[nums[0]];
    while (slow != fast) {
        slow = nums[slow];
        fast = nums[nums[fast]];
    }
    // 找链表环入口
    fast = 0;
    while (slow != fast) {
        slow = nums[slow];
        fast = nums[fast];
    }
    return slow;
}