面試題64. 求1+2+…+n
題目來源：力扣（LeetCode）https://leetcode-cn.com/problems/qiu-12n-lcof
題目
求 1+2+...+n ，要求不能使用乘除法蔫饰、for、while浊伙、if频伤、else原杂、switch弥喉、case等關(guān)鍵字及條件判斷語句（A?B:C）允青。
示例 1：
輸入: n = 3
輸出: 6
示例 2：
輸入: n = 9
輸出: 45
限制：
- 1 <= n <= 10000
解題思路
在這道題目中，有許多的條件限制蒋得。我們先來看能夠使用哪些辦法來解決级及？例如：等差數(shù)列求和，迭代额衙，遞歸
等差數(shù)列求和
先看等差數(shù)列求和创千，這里直接將公式套上就可以，直接看代碼：
class Solution:
def sumNums(self, n: int) -> int:
return (1 + n) * n / 2
但是這里有個問題入偷，這里使用了乘法和除法，先將這個辦法排除械哟。
迭代
使用迭代的話疏之，要么使用 while 語句，要么使用 for 語句暇咆，這里同樣被題目所限制锋爪，所以同樣不可取。這里同樣將代碼貼出來爸业，但是不采納其骄，僅閱讀即可。
class Solution:
def sumNums(self, n: int) -> int:
ans = 0
for i in range(1, n + 1):
ans += i
return ans
遞歸
正常來說扯旷，我們使用遞歸的方法都需要先設(shè)定終止條件拯爽，這里一定會用到條件語句 if，那這樣钧忽，同樣不符合題意毯炮。不過先看下如何實現(xiàn)：
class Solution:
def sumNums(self, n: int) -> int:
if n == 1:
return 1
n += sumNums(n-1)
return n
我們知道，邏輯運算符有個短路性質(zhì)耸黑。假設(shè)有條件 a桃煎、b，有這樣的性質(zhì)大刊，對于表達式 a and b为迈，如果 a 是 False 的話，那么 a and b，一定也是 False葫辐，所以不會去執(zhí)行 b搜锰。
對于 a or b 這個表達式，如果 a 是 True另患，那么 a or b 也就能確定結(jié)果是 True纽乱，所以不會執(zhí)行 b。
現(xiàn)在使用這個短路的性質(zhì)昆箕，嘗試修改遞歸方法的代碼部分（使用 and 或者 or 都可以）鸦列。
具體代碼如下。
代碼實現(xiàn)
# code 1
class Solution:
def __init__(self):
self.ans = 0
def sumNums(self, n: int) -> int:
n == 1 or self.sumNums(n-1)
self.ans += n
return self.ans
# code 2
class Solution:
def __init__(self):
self.ans = 0
def sumNums(self, n: int) -> int:
n > 1 and self.sumNums(n-1)
self.ans += n
return self.ans
實現(xiàn)結(jié)果
總結(jié)
- 先羅列可以解決該問題的一些方法鹏倘，例如：等差數(shù)列求和薯嗤，迭代，遞歸纤泵；
- 使用這些方法解決問題的同時骆姐，查看是否符合題意，不符合的剔除捏题；
- 遞歸的終止條件玻褪，一般情況下都會使用 if 條件進行判斷，這里使用邏輯運算符的短路性質(zhì)公荧，替代 if 語句去確定遞歸的終止條件带射，進而解決此問題。
以上就是本篇幅的主要內(nèi)容循狰，若您覺得文章可以窟社，歡迎關(guān)注。公眾號《書所集錄》同步更新绪钥，同樣歡迎關(guān)注灿里。
