Description
Given an array of integers nums, return the number of good pairs.
A pair (i, j) is called good if nums[i] == nums[j] and i < j.
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
Solutions
Solution 1: Counting
Traverse the array, and for each element x, count how many elements before it are equal to x. This count represents the number of good pairs formed by x and the previous elements. After traversing the entire array, we obtain the answer.
The time complexity is O(n), and the space complexity is O(C). Here, n is the length of the array, and C is the range of values in the array. In this problem, C = 101.
PythonJavaC++GoTypeScriptRustJavaScriptPHPC
class Solution:
def numIdenticalPairs(self, nums: List[int]) -> int:
ans = 0
cnt = Counter()
for x in nums:
ans += cnt[x]
cnt[x] += 1
return ans(code-box)
class Solution {
public int numIdenticalPairs(int[] nums) {
int ans = 0;
int[] cnt = new int[101];
for (int x : nums) {
ans += cnt[x]++;
}
return ans;
}
}(code-box)
class Solution {
public:
int numIdenticalPairs(vector<int>& nums) {
int ans = 0;
int cnt[101]{};
for (int& x : nums) {
ans += cnt[x]++;
}
return ans;
}
};(code-box)
func numIdenticalPairs(nums []int) (ans int) {
cnt := [101]int{}
for _, x := range nums {
ans += cnt[x]
cnt[x]++
}
return
}(code-box)
function numIdenticalPairs(nums: number[]): number {
const cnt: number[] = Array(101).fill(0);
let ans = 0;
for (const x of nums) {
ans += cnt[x]++;
}
return ans;
}(code-box)
impl Solution {
pub fn num_identical_pairs(nums: Vec<i32>) -> i32 {
let mut ans = 0;
let mut cnt = [0; 101];
for &x in nums.iter() {
ans += cnt[x as usize];
cnt[x as usize] += 1;
}
ans
}
}(code-box)
/**
* @param {number[]} nums
* @return {number}
*/
var numIdenticalPairs = function (nums) {
const cnt = Array(101).fill(0);
let ans = 0;
for (const x of nums) {
ans += cnt[x]++;
}
return ans;
};(code-box)
class Solution {
/**
* @param Integer[] $nums
* @return Integer
*/
function numIdenticalPairs($nums) {
$ans = 0;
$cnt = array_fill(0, 101, 0);
foreach ($nums as $x) {
$ans += $cnt[$x]++;
}
return $ans;
}
}(code-box)
int numIdenticalPairs(int* nums, int numsSize) {
int cnt[101] = {0};
int ans = 0;
for (int i = 0; i < numsSize; i++) {
ans += cnt[nums[i]]++;
}
return ans;
}(code-box)
