等差数列求和公式,求解《829. 连续整数求和》

k 个连续数字的等差数列

连续数字的起始数字为 x,终止数字为 x + k - 1,求和 (x + x + k - 1) * k / 2 = n
x = (n - k (k - 1) / 2) / kk (k - 1) / 2 等价于 [0, k - 1] 等差数列和 sum
x 存在,则连续数字之和 = n 的组合存在

例题

829. 连续整数求和

给定一个正整数 n,返回 连续正整数满足所有数字之和为 n 的组数 。
示例 1:
输入: n = 5
输出: 2
解释: 5 = 2 + 3,共有两组连续整数([5],[2,3])求和后为 5。

答案

等差数列

var consecutiveNumbersSum = function(n) {
  // n = (x + x + k - 1) * k / 2 -> k * x = n - (0 + k - 1) * k / 2
  let sum = r = 0
  for (let k = 1; sum < n; k++) {
    if ((n - sum) % k === 0) r++
    sum += k
  }
  return r
};
function consecutiveNumbersSum(n: number): number {
  let sum = 0, r = 0
  for (let k = 1; sum < n; k++) {
    if ((n - sum) % k === 0) r++
    sum += k
  }
  return r
};
class Solution {
  function consecutiveNumbersSum($n) {
    $sum = $r = 0;
    for ($k = 1; $sum < $n; $k++) {
      if (($n - $sum) % $k === 0) $r++;
      $sum += $k;
    }
    return $r;
  }
}
func consecutiveNumbersSum(n int) int {
  sum, r := 0, 0
  for k := 1; sum < n; k++ {
    if (n - sum) % k == 0 {
      r++
    }
    sum += k
  }
  return r
}
class Solution {
  public int consecutiveNumbersSum(int n) {
    int sum = 0, r = 0;
    for (int k = 1; sum < n; k++) {
      if ((n - sum) % k == 0) r++;
      sum += k;
    }
    return r;
  }
}
class Solution:
  def consecutiveNumbersSum(self, n: int) -> int:
    sum, r, k = 0, 0, 1
    while sum < n:
      if (n - sum) % k == 0: r += 1
      sum += k
      k += 1
    return r
def consecutive_numbers_sum(n)
  sum = r = 0
  k = 1
  while sum < n do
    if (n - sum) % k == 0 then
      r += 1
    end
    sum += k
    k += 1
  end
  return r
end
int consecutiveNumbersSum(int n){
  int sum = 0, r = 0;
  for (int k = 1; sum < n; k++) {
    if ((n - sum) % k == 0) r++;
    sum += k;
  }
  return r;
}
public class Solution {
  public int ConsecutiveNumbersSum(int n) {
    int sum = 0, r = 0;
    for (int k = 1; sum < n; k++) {
      if ((n - sum) % k == 0) r++;
      sum += k;
    }
    return r;
  }
}
class Solution {
public:
  int consecutiveNumbersSum(int n) {
    int sum = 0, r = 0;
    for (int k = 1; sum < n; k++) {
      if ((n - sum) % k == 0) r++;
      sum += k;
    }
    return r;
  }
};