Given an array of integers nums.
A pair (i,j) is called good if nums[i] == nums[j] and i < j.
Return the number of good pairs.
Example 1:
Input: nums = [1,2,3,1,1,3] Output: 4 Explanation: There are 4 good pairs (0,3), (0,4), (3,4), (2,5) 0-indexed.
Example 2:
Input: nums = [1,1,1,1] Output: 6 Explanation: Each pair in the array are good.
Example 3:
Input: nums = [1,2,3] Output: 0
Constraints:
1 <= nums.length <= 1001 <= nums[i] <= 100
Solution 1: Brute Force
Enumerate all the pairs.
Time complexity: O(n^2)
Space complexity: O(1)
C++
|
1 2 3 4 5 6 7 8 9 10 |
class Solution { public: int numIdenticalPairs(vector<int>& nums) { int ans = 0; for (int i = 0; i < nums.size(); ++i) for (int j = i + 1; j < nums.size(); ++j) ans += nums[i] == nums[j]; return ans; } }; |
Java
|
1 2 3 4 5 6 7 8 9 |
class Solution { public int numIdenticalPairs(int[] nums) { int ans = 0; for (int i = 0; i < nums.length; ++i) for (int j = i + 1; j < nums.length; ++j) if (nums[i] == nums[j]) ++ans; return ans; } } |
Python3
|
1 2 3 4 5 6 7 8 |
class Solution: def numIdenticalPairs(self, nums: List[int]) -> int: n = len(nums) ans = 0 for i in range(n): for j in range(i + 1, n): if nums[i] == nums[j]: ans += 1 return ans |
Solution 2: Hashtable
Store the frequency of each number so far, when we have a number x at pos j, and it appears k times before. Then we can form additional k pairs.
Time complexity: O(n)
Space complexity: O(range)
C++
|
1 2 3 4 5 6 7 8 9 10 11 |
// Author: Huahua class Solution { public: int numIdenticalPairs(vector<int>& nums) { int ans = 0; vector<int> f(101); for (int i = 0; i < nums.size(); ++i) ans += f[nums[i]]++; return ans; } }; |
Java
|
1 2 3 4 5 6 7 8 9 10 |
// Author: Huahua class Solution { public int numIdenticalPairs(int[] nums) { int ans = 0; int[] f = new int[101]; for (int i = 0; i < nums.length; ++i) ans += f[nums[i]]++; return ans; } } |
Python3
|
1 2 3 4 5 6 7 8 9 |
# Author: Huahua class Solution: def numIdenticalPairs(self, nums: List[int]) -> int: f = defaultdict(int) ans = 0 for x in nums: ans += f[x] f[x] += 1 return ans |
请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Paypal
Venmo
huahualeetcode
huahualeetcode
微信打赏
Be First to Comment