829. 連續整數求和

給定一個正整數 N，試求有多少組連續正整數滿足所有數字之和為 N?

輸入: 5 輸出: 2 解釋: 5 = 5 = 2 + 3，共有兩組連續整數([5],[2,3])求和後為 5。

第一版本：

錯誤理解題意 以為是尋找連續多少個元素累計等於N

step

1. 2次循環遍歷數組，求任意2個連續序列 如果等於 找到

class Solution {public: int consecutiveNumbersSum(int N) {  int count =0; int sum=0; for (int i=1;iN) {  sum=0; count=0; break; } } }  return count; }};

第二版本：

輸入: 15輸出: 4解釋: 15 = 15 = 8 + 7 = 4 + 5 + 6 = 1 + 2 + 3 + 4 + 5

提交結果：超出時間限制 最後執行的輸入： 68188380

int consecutiveNumbersSum(int N) {  int count =0; int sum=0; for (int i=1;i<=N;i++) { sum=0; for(int j=i;j<=N;j++) { sum +=j;  if(sum ==N) { count++; break; }else if (sum >N) {  break; } } }  return count; }

複雜度： 時間 o(n2)

遞歸 dp 很難用不到 如何在優化？

數字之和為N

數學求和問題

第三版本：

重新理解題意：

快速找出連續序列的和等於N

```

N = a + (a+1) + (a+2) + .. + (a+L)

=> N = (L+1)*a + (L*(L+1))/2

=> a = (N- L*(L+1)/2)/(L+1)

```

```

int consecutiveNumbersSum(int N) {

int count = 1;

for( int k = 2; k < sqrt( 2 * N ); k++ ) {

if ( ( N - ( k * ( k - 1 )/2) ) % k == 0) count++;

}

return count;

}

```

https://www.geeksforgeeks.org/count-ways-express-number-sum-consecutive-numbers/

https://www.youtube.com/watch?v=S2OUa--lOm4

閱讀更多 JiaGouS 的文章

關鍵字: 等於 Numbers 技術