Leetcode 2364. Count Number of Bad Pairs

[Woodyiiiiiii]

Method: hash
Key points:

1. convert varying condition to constant condition, that is to convert "j - i != nums[j] - nums[i]" to "j - nums[j] != i - nums[i]"
2. use reverse method, that is to "i - prev"

class Solution {
    public long countBadPairs(int[] nums) {
        long ans = 0;
        int n = nums.length;
        Map<Integer, Integer> map = new HashMap<>();
        
        // convert "j - i != nums[j] - nums[i]" to "j - nums[j] != i - nums[i]"
        for (int i = 0; i < n; ++i) {
            int prev = map.getOrDefault(i - nums[i], 0);
            // prev represents the number of equal, so need "i - prev"
            ans += (i - prev);
            map.put(i - nums[i], prev + 1);
        }
        
        return ans;
    }
}

---

• https://leetcode.com/problems/count-number-of-bad-pairs/