主題
題目連結(jié)：
題目意譯：
給定一個索引值從 0 開始且大小為 n 的整數(shù)陣列 nums，以及兩整數(shù) lower 和 upper，回傳公平數(shù)對之數(shù)量。
一個數(shù)對 (i, j) 是公平的，代表著：
0 ≦ i < j < n；且
lower ≦ nums[i] + nums[j] ≦ upper
限制：
1 ≦ nums.length ≦ 10 ^ 5
nums.length == n
-10 ^ 9 ≦ nums[i] ≦ 10 ^ 9
-10 ^ 9 ≦ lower ≦ upper ≦ 10 ^ 9
範例測資：
範例 1：
輸入： nums = [0,1,7,4,4,5], lower = 3, upper = 6
輸出： 6
解釋： 裡面有 6 個公平數(shù)對：(0,3) 、 (0,4) 、 (0,5) 、 (1,3) 、 (1,4) 和 (1,5)。
範例 2：
輸入： nums = [1,7,9,2,5], lower = 11, upper = 11
輸出： 1
解釋： 裡面只有一個公平數(shù)對：(2,3)。
解題思維：
如果現(xiàn)在我們有一個函式 F(x)，其可以統(tǒng)計出所有 nums[i] + nums[j] ≦ x 的數(shù)對（i < j）之數(shù)量。
則題目的所求答案可以寫成 F(upper) - F(lower - 1)。
那要怎麼計算這個 F(x) 呢？
可以看到把 nums 中的數(shù)字由小排到大，實際上不會影響 F(x) 之值（只是有些數(shù)對的 i 和 j 會交換身分）。
因此我們先把 nums 的數(shù)字由小排到大，並定義兩個指標 L 、 R 來分別指向（排序後的）nums[0] 以及 nums[nums.length - 1]。
接著我們要找出每一個 nums[i] 存在著多少 nums[j] 使得 nums[i] + nums[j] ≦ x 且 i < j。而這個可以使用上面定義的 L 和 R 來找到：
只要 nums[L] + nums[R] > x 且 L < R，就將 R 減去 1。
而最後 R 停下的位置即是對於 i = L 且在 nums[i] + nums[j] ≦ x 情況下，nums[j] 最大的時候。
因此對於 i = L 來說，我們會有 R - L 個滿足 nums[i] + nums[j] ≦ x 的數(shù)對。一開始 L = 0，所以一開始這樣做我們會找出 i = 0 時有多少數(shù)對滿足條件。
而對於兩個相鄰的 i 值（也就是說 i = L 和 i = L + 1），可以看到後者的 R 值絕對不會大過前者的 R 值（因為 nums 有排序過了，因此滿足 nums[L] ≦ nums[L + 1]）。所以我們可以沿用前一次求 i = L 最後的 R 值，來求出 i = L + 1 最後的 R 值。而我們可以重複這個步驟直到 L ≧ R 為止。
而過程中所有的「R - L」之值總和即為 F(x)。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
