最近在準(zhǔn)備算法面試的同學(xué)應(yīng)該都遇到過“大數(shù)相加”這類經(jīng)典問題。力扣LeetCode第 415 題“字符串相加”正是這類問題的典型代表。題目看似簡單但能很好地考察我們對字符串操作、進位處理以及邊界條件的把控能力。很多同學(xué)在初次嘗試時容易在字符與數(shù)字轉(zhuǎn)換、循環(huán)終止條件或最高位進位等細節(jié)上出錯。本文將圍繞力扣 415. 字符串相加這道題從題目解析、思路分析、代碼實現(xiàn)到復(fù)雜度分析進行一次完整的拆解。我們會提供多種語言Python, Java, JavaScript的清晰解法并深入探討其中的關(guān)鍵技巧和易錯點。無論你是剛開始刷題的新手還是想鞏固基礎(chǔ)算法的同學(xué)都能從中獲得清晰的解題路徑和可復(fù)用的代碼模板。1. 題目背景與核心概念1.1 題目描述力扣第 415 題“字符串相加”的官方描述如下給定兩個字符串形式的非負整數(shù)num1和num2計算它們的和并以字符串形式返回。注意你不能使用任何內(nèi)建的用于處理大整數(shù)的庫比如BigInteger也不能直接將輸入的字符串轉(zhuǎn)換為整數(shù)形式。num1和num2的長度都小于 5100。num1和num2都只包含數(shù)字0-9。num1和num2都不包含任何前導(dǎo)零除了數(shù)字0本身。示例 1輸入num1 11, num2 123 輸出134示例 2輸入num1 456, num2 77 輸出533示例 3輸入num1 0, num2 0 輸出01.2 問題本質(zhì)與考察點這道題的核心是模擬人工豎式加法的過程。我們從小學(xué)習(xí)的加法就是從個位開始逐位相加處理進位最后得到結(jié)果。題目禁止使用大數(shù)庫和直接轉(zhuǎn)整數(shù)就是為了讓我們手動實現(xiàn)這個過程。它主要考察以下幾個能力字符串的基本操作如何從字符串中按位取出數(shù)字。雙指針或索引的運用如何從兩個字符串的末尾個位開始向前遍歷。進位Carry的處理這是本題的核心邏輯需要仔細處理相加后進位值的計算與傳遞。邊界條件處理包括兩個字符串長度不同、最高位相加后產(chǎn)生新進位如 “9” “1” “10”、以及輸入為 “0” 的情況。結(jié)果字符串的構(gòu)建由于我們從個位開始計算得到的結(jié)果數(shù)字順序是反的最后需要反轉(zhuǎn)。理解這些考察點是寫出健壯、高效代碼的關(guān)鍵。2. 環(huán)境準(zhǔn)備與解題思路2.1 解題環(huán)境說明對于算法題我們通常不需要復(fù)雜的項目環(huán)境。你只需要一個在線的力扣刷題平臺或者本地的代碼編輯器如 VS Code, PyCharm, IntelliJ IDEA。掌握一門編程語言的基礎(chǔ)語法本文以 Python, Java, JavaScript 為例。理解基本的字符串和數(shù)組操作。本文的代碼示例均假設(shè)在力扣的答題環(huán)境中運行即你只需要實現(xiàn)Solution類中的特定方法。代碼可以直接復(fù)制到力扣的代碼編輯器中提交。2.2 核心算法思路豎式加法模擬解決此問題的通用思路可以分解為以下幾步初始化定義兩個指針i和j分別指向num1和num2的末尾即個位。定義一個變量carry來存儲進位值初始為0。定義一個列表或StringBuilderres來存儲計算結(jié)果的每一位注意是逆序存儲的。循環(huán)計算只要i 0或j 0或carry ! 0就繼續(xù)循環(huán)。carry ! 0這個條件是為了處理最高位相加后仍有進位的情況例如 “999” “1”。在循環(huán)體內(nèi) a. 獲取當(dāng)前位數(shù)字如果指針有效0則通過ord(num1[i]) - ord(0)或int(num1[i])等方式將字符轉(zhuǎn)為數(shù)字否則當(dāng)前位數(shù)字視為0。 b. 計算當(dāng)前位和sum digit1 digit2 carry。 c. 處理進位和當(dāng)前位結(jié)果當(dāng)前位結(jié)果應(yīng)放入res為sum % 10。新的進位carry sum // 10。 d. 將當(dāng)前位結(jié)果數(shù)字轉(zhuǎn)換為字符并添加到res中。 e. 移動指針i--,j--。反轉(zhuǎn)并返回結(jié)果循環(huán)結(jié)束后res中存儲的是從個位到最高位的數(shù)字字符。需要將res反轉(zhuǎn)然后連接成一個字符串返回。流程圖示意開始 | 初始化 i, j, carry0, res[] | while (i0 或 j0 或 carry0): | digit1 num1[i] if i0 else 0 | digit2 num2[j] if j0 else 0 | total digit1 digit2 carry | carry total // 10 | res.append(str(total % 10)) | i--, j-- | 反轉(zhuǎn) res | 將 res 連接成字符串 | 返回字符串 結(jié)束3. 多語言代碼實現(xiàn)與逐行解析下面我們分別用 Python、Java 和 JavaScript 來實現(xiàn)上述算法并對關(guān)鍵代碼行進行詳細解釋。3.1 Python 實現(xiàn)Python 的字符串操作非常靈活代碼也最為簡潔。class Solution: def addStrings(self, num1: str, num2: str) - str: # 初始化指針和進位 i, j len(num1) - 1, len(num2) - 1 carry 0 res [] # 使用列表存儲結(jié)果字符效率高于字符串拼接 # 循環(huán)條件任一字符串還有位或者還有進位 while i 0 or j 0 or carry: # 獲取當(dāng)前位的數(shù)字如果指針已越界則視為0 digit1 int(num1[i]) if i 0 else 0 digit2 int(num2[j]) if j 0 else 0 # 計算當(dāng)前位的總和包括進位 total digit1 digit2 carry # 計算新的進位和當(dāng)前位的結(jié)果 carry total // 10 digit total % 10 # 將當(dāng)前位數(shù)字轉(zhuǎn)為字符并加入結(jié)果列表此時是逆序 res.append(str(digit)) # 移動指針 i - 1 j - 1 # 將結(jié)果列表反轉(zhuǎn)并連接成字符串 # 因為我們是按個位、十位...的順序添加的所以需要反轉(zhuǎn) return .join(res[::-1])代碼解析int(num1[i])Python 中可以直接將數(shù)字字符如5轉(zhuǎn)換為整數(shù)5。res []使用列表append操作來構(gòu)建結(jié)果其時間復(fù)雜度為 O(1)最后用join拼接。這比在循環(huán)中反復(fù)進行字符串拼接str str效率高得多因為字符串在 Python 中是不可變對象每次拼接都會生成新對象。while i 0 or j 0 or carry:這是循環(huán)的關(guān)鍵條件。or carry確保了即使兩個字符串都遍歷完了如果最后還有進位如“1” “9”循環(huán)還會再進行一次將進位1作為最高位加入結(jié)果。res[::-1]這是 Python 的切片語法表示將列表res完全反轉(zhuǎn)。.join(...)將反轉(zhuǎn)后的字符列表連接成一個完整的字符串。3.2 Java 實現(xiàn)Java 的實現(xiàn)需要更多的手動字符處理并通常使用StringBuilder來高效構(gòu)建字符串。class Solution { public String addStrings(String num1, String num2) { // 初始化指針和進位 int i num1.length() - 1; int j num2.length() - 1; int carry 0; // 使用 StringBuilder 構(gòu)建結(jié)果效率高 StringBuilder res new StringBuilder(); // 循環(huán)條件任一字符串還有位或者還有進位 while (i 0 || j 0 || carry 0) { // 獲取當(dāng)前位的數(shù)字如果指針已越界則視為0 int digit1 (i 0) ? num1.charAt(i) - 0 : 0; int digit2 (j 0) ? num2.charAt(j) - 0 : 0; // 計算當(dāng)前位的總和包括進位 int sum digit1 digit2 carry; // 計算新的進位 carry sum / 10; // 計算當(dāng)前位的結(jié)果 int digit sum % 10; // 將當(dāng)前位數(shù)字加入 StringBuilder此時是逆序 res.append(digit); // 移動指針 i--; j--; } // 將結(jié)果反轉(zhuǎn)并轉(zhuǎn)換為字符串 // 因為 append 是順序添加我們得到的是個位在前所以需要反轉(zhuǎn) return res.reverse().toString(); } }代碼解析num1.charAt(i) - 0這是 Java 中將字符數(shù)字轉(zhuǎn)換為整數(shù)的經(jīng)典方法。字符‘0’到‘9’在 ASCII 表中是連續(xù)的‘0’的值是 48?！?’ - ‘0’的結(jié)果就是53 - 48 5。StringBuilder在 Java 中String是不可變的。在循環(huán)中拼接字符串會產(chǎn)生大量臨時對象影響性能。StringBuilder是可變的字符序列append操作效率很高。res.reverse().toString()StringBuilder的reverse()方法會原地反轉(zhuǎn)字符序列然后toString()將其轉(zhuǎn)換為String返回。循環(huán)條件carry 0與carry ! 0在此處等價因為進位值carry只可能是 0 或 1兩個一位數(shù)相加最大為 99119進位最大為1。但寫成carry 0更直觀。3.3 JavaScript 實現(xiàn)JavaScript 的實現(xiàn)思路與 Python 和 Java 類似注意其數(shù)字轉(zhuǎn)換和字符串構(gòu)建方式。/** * param {string} num1 * param {string} num2 * return {string} */ var addStrings function(num1, num2) { let i num1.length - 1; let j num2.length - 1; let carry 0; const res []; // 使用數(shù)組存儲結(jié)果數(shù)字 while (i 0 || j 0 || carry) { // 獲取當(dāng)前位的數(shù)字如果指針已越界則視為0 const digit1 i 0 ? parseInt(num1[i]) : 0; const digit2 j 0 ? parseInt(num2[j]) : 0; // 計算當(dāng)前位的總和包括進位 const sum digit1 digit2 carry; // 計算新的進位和當(dāng)前位的結(jié)果 carry Math.floor(sum / 10); const digit sum % 10; // 將當(dāng)前位數(shù)字加入數(shù)組此時是逆序 res.push(digit); // 移動指針 i--; j--; } // 將數(shù)組反轉(zhuǎn)并連接成字符串 // 因為 push 是順序添加我們得到的是個位在前所以需要反轉(zhuǎn) return res.reverse().join(); };代碼解析parseInt(num1[i])JavaScript 中parseInt可以將字符串轉(zhuǎn)換為整數(shù)。num1[i]是一個字符parseInt(‘5’)得到5。也可以使用num1.charCodeAt(i) - ‘0’.charCodeAt(0)但parseInt更直觀。Math.floor(sum / 10)在 JavaScript 中除法/默認返回浮點數(shù)。我們需要使用Math.floor來獲取整數(shù)商即進位值。因為兩個一位數(shù)相加最大為 19sum / 10的結(jié)果只能是 0 或 1Math.floor可以正確獲取。res.push(digit)和res.reverse().join(‘’)使用數(shù)組push方法添加元素最后反轉(zhuǎn)數(shù)組并用join方法拼接成字符串。這與 Python 的列表操作類似。4. 復(fù)雜度分析與算法評價4.1 時間復(fù)雜度我們使用了一個while循環(huán)循環(huán)的次數(shù)最多為max(len(num1), len(num2)) 11 是處理最高位進位的情況。循環(huán)體內(nèi)的操作取數(shù)字、計算、追加字符都是常數(shù)時間O(1)。因此總的時間復(fù)雜度為O(max(N, M))其中 N 和 M 分別是兩個輸入字符串的長度。這是一個非常高效的線性時間復(fù)雜度。4.2 空間復(fù)雜度我們使用了一個額外的列表/數(shù)組/StringBuilder 來存儲結(jié)果其長度最多為max(N, M) 1。除了輸入和輸出我們只使用了幾個整型變量i,j,carry,digit1,digit2,sum。因此總的空間復(fù)雜度為O(max(N, M))主要用于存儲結(jié)果字符串。這是無法避免的因為我們必須返回一個新的字符串。4.3 算法評價優(yōu)點直觀易懂完全模擬了人工計算加法的過程邏輯清晰。高效時間和空間復(fù)雜度都是線性的是最優(yōu)解。健壯正確處理了長度不等、最高位進位、全零輸入等邊界情況。缺點無明顯缺點是該問題的標(biāo)準(zhǔn)解法。5. 常見錯誤與排查思路在實現(xiàn)“字符串相加”時初學(xué)者常會遇到以下幾個問題問題現(xiàn)象常見原因解決思路輸出結(jié)果比預(yù)期少一位例如 “99” “1” 輸出 “00”循環(huán)條件缺少對最后進位的判斷。當(dāng)最高位相加產(chǎn)生進位時循環(huán)在遍歷完字符串后即停止漏掉了進位。將循環(huán)條件改為 while (i 0輸出結(jié)果順序是反的例如 “11” “123” 輸出 “431”忘記反轉(zhuǎn)結(jié)果。我們從個位開始計算并將結(jié)果依次存入列表得到的是逆序的字符串。在返回結(jié)果前務(wù)必對存儲結(jié)果的列表或StringBuilder進行反轉(zhuǎn)操作。遇到非數(shù)字字符或空字符串時報錯題目已保證輸入是合法數(shù)字字符串但自己測試時可能輸入錯誤。代碼未做防御性檢查。對于生產(chǎn)代碼可以在開頭添加輸入驗證。對于算法題通常信任題目約束。確保測試用例符合題目要求。在 Java 中使用String拼接導(dǎo)致性能極差在循環(huán)內(nèi)使用result digit result或result digit。每次操作都會創(chuàng)建新的String對象。務(wù)必使用StringBuilder來構(gòu)建字符串。JavaScript 中進位計算錯誤得到小數(shù)使用sum / 10直接賦值給carry在 JavaScript 中這會得到浮點數(shù)如 0.1。使用Math.floor(sum / 10)或~~(sum / 10)來獲取整數(shù)進位。Python 中結(jié)果字符串包含方括號和逗號錯誤地直接返回了列表res而不是拼接后的字符串。使用return .join(res[::-1])確保返回的是字符串。自檢清單循環(huán)條件是否包含了carry ! 0指針越界時當(dāng)前位數(shù)字是否正確地設(shè)為 0進位carry的計算是否正確total // 10或sum / 10取整當(dāng)前位結(jié)果是否正確total % 10是否將數(shù)字轉(zhuǎn)換成了字符再存儲最終返回前是否反轉(zhuǎn)了結(jié)果序列對于輸入“0”和“0”是否能正確返回“0”而不是“”或[]6. 變種問題與最佳實踐掌握了“字符串相加”后你可以輕松解決一系列類似問題。同時遵循一些最佳實踐能讓你的代碼更健壯、更優(yōu)雅。6.1 相關(guān)變種問題力扣 2. 兩數(shù)相加這是“字符串相加”的鏈表版本。給你兩個非空鏈表表示兩個非負整數(shù)每位數(shù)字逆序存儲。你需要返回一個同樣形式的鏈表。解題思路完全一致只是數(shù)據(jù)結(jié)構(gòu)從字符串/數(shù)組變成了鏈表。力扣 67. 二進制求和給你兩個二進制字符串返回它們的和用二進制表示。算法一模一樣只是把進制從10改為2。計算進位時carry sum // 2當(dāng)前位結(jié)果為sum % 2。大數(shù)相乘力扣 43. 字符串相乘這是更復(fù)雜的題目。核心思路是模擬豎式乘法但需要嵌套循環(huán)并處理好每一層部分積的累加和進位。大數(shù)減法和除法思路類似但減法需要考慮借位處理起來比加法稍復(fù)雜。除法則是模擬豎式除法。6.2 代碼最佳實踐使用雙指針從末尾遍歷這是處理字符串/數(shù)組表示的數(shù)字計算的最標(biāo)準(zhǔn)模式。統(tǒng)一使用while (i 0 || j 0 || carry)作為循環(huán)條件這個條件最完備能覆蓋所有情況。使用列表/StringBuilder/數(shù)組存儲中間結(jié)果避免在循環(huán)中進行字符串拼接這是保證算法效率的關(guān)鍵。清晰命名變量使用carry(進位)、digit1/digit2(當(dāng)前位數(shù)字)、sum/total(總和)、res(結(jié)果) 等有意義的變量名提高代碼可讀性。添加注釋對于算法題清晰的注釋能幫助面試官快速理解你的思路尤其是在處理進位和邊界條件的地方?？紤]邊界用例在寫完代碼后主動測試以下用例“0” “0”“1” “9”(產(chǎn)生進位)“999” “1”(多位數(shù)進位)“123” “4567”(長度不同)手動模擬對于復(fù)雜的邊界條件可以在紙上或心里手動模擬一遍算法流程確保邏輯正確。6.3 面試技巧如果這道題出現(xiàn)在面試中先溝通不要急于寫代碼。先向面試官復(fù)述題目確認理解無誤例如數(shù)字是否非負是否可能為空。闡述思路說出你要模擬豎式加法使用雙指針從末尾開始用一個變量記錄進位。邊寫邊講在寫代碼時解釋你在做什么“我現(xiàn)在初始化兩個指針和進位變量…”“這個循環(huán)條件是為了處理最高位進位…”。寫完測試寫完后用1-2個簡單的例子如“11” “123”和1個邊界例子如“999” “1”來演示代碼運行過程。分析復(fù)雜度主動分析時間和空間復(fù)雜度并說明這是最優(yōu)解。7. 總結(jié)與擴展學(xué)習(xí)力扣 415 題“字符串相加”是一道非常好的入門算法題它不涉及復(fù)雜的數(shù)據(jù)結(jié)構(gòu)但完整地考察了基本的編程能力循環(huán)、條件判斷、數(shù)據(jù)類型轉(zhuǎn)換、邊界處理以及字符串/數(shù)組操作。掌握它就掌握了解決所有“大數(shù)運算”模擬題的基礎(chǔ)框架。核心要點回顧模擬人工計算從最低位末尾開始逐位相加處理進位。循環(huán)條件三要素指針i, 指針j, 進位carry缺一不可。高效構(gòu)建結(jié)果使用可變?nèi)萜鱌ython list, Java StringBuilder, JS Array存儲逆序結(jié)果最后反轉(zhuǎn)。小心邊界長度不同的字符串、最高位的進位、全零輸入。下一步學(xué)習(xí)建議鞏固嘗試獨立完成力扣 67. 二進制求和和力扣 2. 兩數(shù)相加感受算法框架的復(fù)用性。挑戰(zhàn)嘗試解決力扣 43. 字符串相乘這是大數(shù)運算的進階版。拓展學(xué)習(xí)更多字符串相關(guān)的高頻題目如反轉(zhuǎn)字符串、驗證回文串、字符串轉(zhuǎn)換整數(shù)等。系統(tǒng)訓(xùn)練將此類“模擬”算法歸入你的知識體系它通常與“數(shù)學(xué)”、“字符串”標(biāo)簽相關(guān)。在力扣上可以按標(biāo)簽或題目列表進行專項練習(xí)。算法學(xué)習(xí)是一個循序漸進的過程。從這道題出發(fā)理解其背后的“模擬”思想并能夠舉一反三你的解題能力就會穩(wěn)步提升。多寫、多練、多總結(jié)是通往算法高手的必經(jīng)之路。