題目連結:
題目意譯:
給定一整數陣列 nums,回傳好數對的數量。
一個數對 (i, j) 如果滿足 nums[i] == nums[j] 且 i < j,則其將被稱為好數對。
限制:
1 ≦ nums.length ≦ 100
1 ≦ nums[i] ≦ 100
範例測資:
範例 1:
輸入: nums = [1,2,3,1,1,3]
輸出: 4
解釋: 有 4 個 (0, 3) 、 (0, 4) 、 (3, 4) 、 (2, 5)(索引值從 0 開始)。
範例 2:
輸入: nums = [1,1,1,1]
輸出: 6
解釋: 陣列中每一個數對都是好數對。
範例 3:
輸入: nums = [1,2,3]
輸出: 0
解題思維:
先把 nums 由小排到大(索引值 i < j 這個條件沒有這麼重要,重要的是數值本身),因此相同數值的數字會排在一起(不過因為這題的數值範圍很小,所以也可以直接開陣列來統計)。接著就掃過一次來統計每一種數字的出現次數。
假設現在有一種數字出現了 C 次,則該種數字會有 C × (C - 1) ÷ 2 個好數對存在於其中。
將每一種數字貢獻的好數對加總即為所求。
此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。