前言

這篇是我在解 HackerRank A Very Big Sum 時的刷題筆記.

題目本身看似只是把陣列全部加總, 但它真正想測的是你有沒有意識到「數字可能大到超出一般整數型別的範圍」. 在 TypeScript 裡這題幾乎是一路平順, 但到了 Java, 若沒有先想清楚 int、long 和 Stream 的差異, 很容易在型別上先翻車.

題目要求與核心考點

題目要求對一個整數陣列進行加總, 但特別標註了數值可能非常大, 單一元素甚至可達 $10^{10}$.

這題真正的考點其實不是加法本身, 而是先確認「你現在用的型別, 能不能安全裝下結果」. 只要型別選錯, 算法再簡單也會在測資裡直接失敗.

跨語言數值型別對照

在處理大數運算時, 先理解語言底層的數值型別很重要. 以下是 Java 與 TypeScript 的對照:

語言型別說明與極限範圍
Javaint32 位元整數, 最大值約 21 億 ($2^{31} - 1$). 遇到這題的高位測資時, 很容易直接溢位.
Javalong64 位元整數, 最大值約 $2^{63} - 1$. 這題應該使用這個型別.
Javafloat32 位元單精度浮點數, 用於帶小數點的數值, 精度較低.
Javadouble64 位元雙精度浮點數, 用於帶小數點的數值, 精度較高.
TypeScriptnumber底層是 64 位元雙精度浮點數, 安全整數範圍可到 $2^{53} - 1$. 這題的加總規模遠小於這個上限, 所以用 number 即可.
TypeScriptbigint任意精度整數. 若遇到超過安全整數範圍的天文數字, 可以用 n 後綴來保證精度.

TypeScript 的歲月靜好

延用上一題的 reduce 寫法, 這題在 TypeScript 幾乎沒有壓力. 只要知道 number 的安全邊界遠大於本題測資規模, 一行就能穩穩過關.

function aVeryBigSum(ar: number[]): number {
  return ar.reduce((a, b) => a + b, 0);
}

Java 的嚴格審查與三種手感測試

面對 $10^{10}$ 等級的數值, Java 必須老老實實使用 long. 我自己在整理時試了三種寫法, 其中有一種還踩到經典的 Lambda 限制.

寫法 A: 傳統 for loop

這是最直覺、也最穩妥的寫法. 先宣告 long sum = 0L, 再直接累加.

long sum = 0L;
for (Long num : ar) {
    sum += num;
}
return sum;

寫法 B: forEach 與 Lambda 的碰撞

原本想用 ar.forEach(num -> sum += num) 直接累加外部變數, 但會遇到編譯錯誤:

local variables referenced from a lambda expression must be final or effectively final

踩坑原因在於 Java 的 Lambda 不允許任意修改外部的區域變數. 這些變數必須是 effectively final, 也就是說在 Lambda 內不能被重新賦值.

理論上可以改用 LongAdder 繞過限制, 但那是為了多執行緒高併發設計的工具, 用在單純陣列加總上其實有點殺雞用牛刀.

寫法 C: Stream API 的流水線

如果不想碰外部狀態, Java 8 的 Stream API 會是更乾淨的選擇. 它把整個過程拆成資料流、型別轉換、終端加總三段, 可讀性很高.

long sum = ar.stream()
             .mapToLong(Long::longValue)
             .sum();

流水線拆解

  1. ar.stream(): 把 List<Long> 展開成資料流, 讓元素開始進入管線.
  2. mapToLong(Long::longValue): 把包裝型別 Long 拆成原生型別 long, 並升級成 LongStream.
  3. sum(): 終端操作, 將所有數值加總後輸出結果.

這種寫法的好處是語意清楚, 沒有副作用, 也不需要手動維護外部累加狀態.

複雜度分析

  • 時間複雜度: $O(N)$, 因為不管是 reduce、for loop 還是 Stream, 都需要把長度為 $N$ 的陣列走訪一次.
  • 空間複雜度: $O(1)$, 只使用固定大小的累加器, 沒有額外隨輸入成長的記憶體需求.

核心體悟

  1. 跨語言解題時, 先確認型別範圍再寫邏輯, 比單純把程式打出來更重要.
  2. Java 的 Lambda 有明確的狀態限制, 遇到需要累加的場景, 傳統 for 迴圈通常最穩.
  3. Stream API 不是只是語法糖, 它能把資料處理過程拆成更清楚的流水線, 也更符合函式式思維.

總結

這題表面上是加總, 實際上是在提醒你: 大數題目先看型別, 再看寫法.

  • TypeScript 因為 number 的安全範圍夠大, 可以直接用 reduce.
  • Java 必須選對 long, 才不會在中途溢位.
  • 若想把程式寫得更乾淨, Stream API 會比手動維護外部變數更自然.

把這個習慣養起來, 後面遇到數值範圍更敏感的題目時, 會少很多不必要的坑.

參考資料