関小君刷题记

题目大意：

Given an integer array arr, count how many elements x there are, such that x + 1 is also in arr.

If there’re duplicates in arr, count them seperately.

Example 1:

Input: arr = [1,2,3]
Output: 2
Explanation: 1 and 2 are counted cause 2 and 3 are in arr.

Example 2:

Input: arr = [1,1,3,3,5,5,7,7]
Output: 0
Explanation: No numbers are counted, cause there's no 2, 4, 6, or 8 in arr.

Example 3:

Input: arr = [1,3,2,3,5,0]
Output: 3
Explanation: 0, 1 and 2 are counted cause 1, 2 and 3 are in arr.

Example 4:

Input: arr = [1,1,2,2]
Output: 2
Explanation: Two 1s are counted cause 2 is in arr.

Example 5:

Input: arr = [1,1,2]
Output: 2
Explanation: Both 1s are counted because 2 is in the array.

Constraints:

• 1 <= arr.length <= 1000
• 0 <= arr[i] <= 1000

---

如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=1426

解题思路分析：

1. 首先遍历一遍数组，统计每种数字的个数。记录在Map中，key为数字，value为该数字出现的个数。
2. 遍历map中的每一个key（数字），对于当前数字，如果map中存在值为key+1的key的话，那么当前key所代表的数字就是一个符合答案的数，将他的个数累加至返回结果。

实现代码：

public int countElements(int[] arr) {
    // 统计数组中每个数字的个数
    Map<Integer, Integer> map = new HashMap<>();
    for(int num : arr){
        int count=map.getOrDefault(num,0);
        map.put(num,count+1);
    }
    // 返回结果
    int res=0;
    // 循环map中的key（所有不重复的数字）
    for(int num : map.keySet()){
        // 如果存在num+1，说明当前数字是符合题意的数字
        if(map.containsKey(num+1)){
            // 将当前数字的个数累加至返回结果
            res+=map.get(num);
        }
    }
    return res;
}

本题解法执行时间为1ms。

Runtime: 1 ms, faster than 87.53% of Java online submissions for Counting Elements.

Memory Usage: 37.2 MB, less than 100.00% of Java online submissions for Counting Elements.

本网站文章均为原创内容，并可随意转载，但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-1426-counting-elements-解题思路分析/