算法筆試模拟題精解之“朋友一生一起走”

線上程式設計介紹

阿裡雲開發者社群線上程式設計産品，針對廣大開發者學習、實踐、面試、應聘、考試認證等打造的免費線上刷題神器。題庫來自筆試模拟題、算法大賽模拟題等，界面整潔明了，操作簡單，為使用者營造專心答題的學習環境。點選連結開始體驗：

https://developer.aliyun.com/coding

本文為大家介紹其中的 第52題：朋友一生一起走 的題目解析，具體如下：

題目描述

題目等級：容易

知識點：數學

檢視題目：朋友一生一起走

Tom想從n個數(1<=n<=1e14)中把“好朋友”挑出來，“好朋友”的定義是相加等于k(1<=k<=1e14)，其中(1,2)和(2,1)算一對，請你幫Tom計算一下1-n中一共有多少對好朋友？

輸入數字總數n和“好朋友”數的和k；

輸出1-n中的好朋友有多少對。

示例1

輸入：

3

5

輸出：

1

解題方法

根據題意可以得出，在不考慮數字範圍的情況下，相加等于 k 的數總共有 k/2 對（如果 k 為偶數，應為 k/2-1 對，此處以 k/2 為例）。也就是說，如果 n 的值大于 k 的值，那麼 k 的所有數對都符合條件，即 1-n 中一共有 k/2 對好朋友。

如果 n 的值小于等于 k，那麼 k 的有些數對會超出 n 的範圍，需要舍棄。

根據n的範圍限制，可以計算得出，需要舍棄掉的對數為（k-n-1）, 即此時一共有 k/2 -（k-n-1）對好朋友，若計算出此數為負值，即好朋友的對數為0。

時間複雜度：O(1)

空間複雜度：O(1)

看完之後是不是有了想法了呢，快來練練手吧>>