輸入一個(gè)正整數(shù) target 泰偿，輸出所有和為 target 的連續(xù)正整數(shù)序列（至少含有兩個(gè)數(shù)）又沾。
序列內(nèi)的數(shù)字由小到大排列叫确，不同序列按照首個(gè)數(shù)字從小到大排列南用。
- 示例 1：
輸入：target = 9
輸出：[[2,3,4],[4,5]]
示例 2：
輸入：target = 15
輸出：[[1,2,3,4,5],[4,5,6],[7,8]]
限制：
1 <= target <= 10^5
題解
按照純數(shù)學(xué)平均數(shù)的想法來做的膀钠，代碼可能寫的比較啰嗦。
- 設(shè)最多能有n個(gè)數(shù)加起來能等于target, 則n >= 2
- 以n >= 2為while循環(huán)條件裹虫，找出這n個(gè)數(shù)字的平均數(shù)肿嘲，注意Python3使用
//進(jìn)行除法會得到向下取整的整數(shù) - 這個(gè)是重點(diǎn)，由于序列每個(gè)數(shù)字都必須為正整數(shù)筑公，所以n個(gè)數(shù)字中最小的數(shù)字必須大于或等于1.
根據(jù)第三點(diǎn)雳窟，可以輕易得出一個(gè)公式：
當(dāng)n為偶數(shù)時(shí)：平均數(shù) - n // 2 + 1 >= 1
舉個(gè)例子，target=9, n=4的時(shí)候匣屡，平均數(shù)為2封救，所以4個(gè)數(shù)字必須是圍繞2組成，并且大小均勻分布捣作，由于n=4誉结，導(dǎo)致數(shù)組有2種情況, 分別為: [0, 1, 2, 3]和[1, 2, 3, 4]，當(dāng)?shù)诙N情況的最小數(shù)字都小于1的時(shí)候虾宇，第一種情況必定也會小于1搓彻，所以此時(shí)的判斷公式為平均數(shù) - n // 2 + 1 >= 1
當(dāng)n為奇數(shù)時(shí)：平均數(shù) - n // 2 >= 1
此時(shí)比較簡單，中位數(shù)就是平均數(shù)嘱朽，所以左右均勻分配旭贬，只需要平均數(shù) - n // 2 >= 1即可。
最后是n = 2的時(shí)候搪泳，由于數(shù)字不能重復(fù)稀轨，只要n是偶數(shù)，那么絕對不可能有2個(gè)一樣的數(shù)字組成這個(gè)target岸军。如果n是奇數(shù)奋刽，則mid為向下取余的數(shù)字瓦侮，必有 奇數(shù)target = mid+(mid+1)
class Solution:
def findContinuousSequence(self, target: int) -> List[List[int]]:
# 最終結(jié)果數(shù)組
result = []
# 初始化target
n = target
while n > 2:
mid = target // n
# 判斷n是否為偶數(shù)
if n % 2 == 0:
if mid - n // 2 + 1 < 1:
# 如果此序列的最小值都小于1，則n-- 循環(huán)繼續(xù)
n -= 1
continue
# 滿足第一種情況
if sum(range(mid - n // 2, mid + n // 2)) == target:
result.append(list(range(mid - n // 2, mid + n // 2)))
# 滿足第二種情況
elif sum(range(mid - n // 2 + 1, mid + n // 2 + 1)) == target:
result.append(list(range(mid - n // 2 + 1, mid + n // 2 + 1)))
else:
# 奇數(shù)時(shí)候佣谐，最小值小于1則繼續(xù)循環(huán)
if mid - n // 2 < 1:
n -= 1
continue
if sum(range(mid - n // 2, mid + n // 2 + 1)) == target:
result.append(list(range(mid - n // 2, mid + n // 2 + 1)))
n -= 1
# 由于n >= 2
if target % 2 != 0:
mid = target // 2
result.append([mid, mid + 1])
return result
可以看到時(shí)間復(fù)雜度還是很多的肚吏，但是內(nèi)存占用比較小，當(dāng)然寫的也比較啰嗦狭魂，慢慢刷吧罚攀！無套路太難了~
