مشکل از ما می خواهد که تعداد جفت های خوب در یک آرایه را پیدا کنیم. یک جفت خوب به عنوان یک جفت (i، j) تعریف می شود که در آن 0 <= i < j < nums.length و nums[i] == nums[j]. به عبارت دیگر، ما باید تعداد رخدادهای یک عنصر را در آرایه بشماریم که شاخص کمتری نسبت به وقوع دیگری از همان عنصر دارند.
یک روش ساده برای حل این مشکل استفاده از حلقه های تو در تو برای مقایسه هر جفت عنصر در آرایه و شمارش جفت های خوب است. حلقه بیرونی روی هر عنصر در آرایه تکرار می شود و حلقه داخلی از عنصر بعدی شروع می شود و آن را با عنصر فعلی مقایسه می کند. اگر عناصر برابر باشند، تعداد جفت های خوب را افزایش می دهیم.
- پیچیدگی زمانی: O(n^2) – حلقه‌های تودرتو روی همه جفت‌های عنصر در آرایه تکرار می‌شوند که منجر به پیچیدگی زمانی درجه دوم می‌شود.
- پیچیدگی فضا: O(1) – ما از مقدار ثابتی از فضای اضافی برای ذخیره تعداد جفت های خوب استفاده می کنیم.
class Solution {
public int numIdenticalPairs(int[] nums) {
int goodPairs = 0;
for (int i = 0; i < nums.length; i++) {
for (int j = i + 1; j < nums.length; j++) {
if (nums[i] == nums[j]) {
goodPairs++;
}
}
}
return goodPairs;
}
}
توجه: این قطعه کد در جاوا است.
