目錄
1. 兩數之和
1.1 題目解析
1.2 解法
1.3 代碼實現
2. 只出現一次的數字II
2.1 題目解析
2.2 解法
2.3 代碼實現
1. 兩數之和
371. 兩整數之和 - 力扣（LeetCode）
給你兩個整數?a?和?b?，不使用?運算符?+?和?-?，計算并返回兩整數之和。
示例 1：
輸入：a = 1, b = 2 輸出：3
示例 2：
輸入：a = 2, b = 3 輸出：5
提示：
-1000 <= a, b <= 1000
1.1 題目解析
本題要求在不使用加減運算符的情況下，計算兩個整數的和。換句話說，要實現“加法”的本質操作：無進位相加 + 進位疊加。
常規解法：
最直觀的想法是直接寫 return a + b;，但是題目顯然禁止這樣。
既然不能用 + -，我們需要模擬“加法”的底層過程。二進制加法本質上有兩部分：
-
無進位相加：用 異或運算 (XOR) 實現，因為相同位相加結果為 0，不同為 1。
-
進位部分：用 與運算 (AND) 再左移一位實現，因為只有 1+1?才會產生進位。
這個過程需要循環，直到沒有進位為止。
思路轉折：
加法能拆解為兩個基本的位運算 → 迭代模擬 → 得到最終和。
這種思路的優點：復雜度始終是 O(1)，因為整數位數是固定的（32 位）。
1.2 解法
用 a ^ b 表示“當前無進位的和”，用 (a & b) << 1 表示“進位”，不斷迭代，直到進位為 0。
公式：
sum = a ^ b
carry = (a & b) << 1
a = sum
b = carry
i）初始化 a, b。
ii）計算無進位和：a ^ b。
iii）計算進位：(a & b) << 1。
iiii）更新 a 和 b。
iiiii）重復，直到進位 b = 0。
iiiiii）返回最終結果 a。
1.3 代碼實現
class Solution {public int getSum(int a, int b) {while (b != 0) {int sum = a ^ b; // 無進位和int carry = (a & b) << 1; // 進位a = sum;b = carry;}return a;}
}
復雜度分析：
-
時間復雜度：O(1)，因為整數位數有限（最多 32 次迭代）。
-
空間復雜度：O(1)，只用常數額外變量。
2. 只出現一次的數字II
137. 只出現一次的數字 II - 力扣（LeetCode）
給你一個整數數組?nums?，除某個元素僅出現?一次?外，其余每個元素都恰出現?三次 。請你找出并返回那個只出現了一次的元素。
你必須設計并實現線性時間復雜度的算法且使用常數級空間來解決此問題。
示例 1：
輸入：nums = [2,2,3,2] 輸出：3
示例 2：
輸入：nums = [0,1,0,1,0,1,99] 輸出：99
提示：
1 <= nums.length <= 3 * 104-231 <= nums[i] <= 231 - 1nums?中，除某個元素僅出現?一次?外，其余每個元素都恰出現?三次
2.1 題目解析
在一個數組里，所有數字都出現三次，只有一個數字出現一次，找出它。
換句話說，本質是：如何在三次重復噪聲中，唯一識別出那個單獨元素。
常規解法：
直觀做法是用哈希表統計頻次，再找頻次為 1 的元素。
哈希表能解決，但空間復雜度是 O(n)，題目要求 O(1)。
因此必須用位運算，直接利用二進制規律。
思路轉折：
每個數的二進制位，若出現三次，總和必能被 3 整除。
只有那個單獨出現一次的數，會在某些二進制位上讓總和不能整除 3。
所以：逐位統計 → 取余 → 重建結果。
這種方法復雜度 O(32n) = O(n)，空間 O(1)
2.2 解法
按位統計每個二進制位出現的次數，模 3 去掉“三次噪聲”，剩下的位拼接成結果。
公式：
bitSum[i] = Σ(num >> i & 1)
if bitSum[i] % 3 != 0 → 結果的第 i 位 = 1
i）初始化結果變量 ret = 0。
ii）遍歷 32 位（因為 int 是 32 位）。
iii）對于每一位，統計所有數在該位上的 1 的個數。
iiii）如果該位 1 的個數 % 3 ≠ 0，說明唯一數在該位上有 1。
iiiii）把該位寫入 ret。
iiiiii）返回 ret。
正確性：三次重復的性質
題目保證：除一個元素外，其余元素都出現三次→ 如果我們單獨看數組中某一位 i，每個出現三次的數會在這位上貢獻 0+0+0=0 或 1+1+1=3。
換句話說：
-
三次重復的數對第 i 位的總和一定是 3 的倍數。
2.3 代碼實現
class Solution {public int singleNumber(int[] nums) {int ret = 0;for (int i = 0; i < 32; i++) {int sum = 0;for (int num : nums) {sum += (num >> i) & 1; // 統計第 i 位}if (sum % 3 != 0) {ret |= (1 << i); // 恢復結果的第 i 位}}return ret;}
}
復雜度分析：
-
時間復雜度：O(32n) ≈ O(n)。
-
空間復雜度：O(1)。
)