统计一个数字在排序数组中出现的次数。
示例 1:
输入: nums = [5,7,7,8,8,10], target = 8 输出: 2
示例 2:
输入: nums = [5,7,7,8,8,10], target = 6 输出: 0
限制： 0 <= 数组长度 <= 50000 （来源：力扣（LeetCode））
思路：哈希表 遍历一次数组，存入哈希表中，哈希表中的key为数组元素，value为数组元素出现的次数： （1）若数组元素存在，将数组元素对应的value+1，即 map.put(num, map.get(num) + 1；。 （2）若不存在就添加新元素。 （3）最后查找哈希表中target对应的value，不存在即返回0
class Solution { public int search(int[] nums, int target) { if (nums.length == 0) return 0; HashMap<Integer, Integer> map = new HashMap<>(); for (int num : nums) { if (map.containsKey(num)) { map.put(num, map.get(num) + 1); } else { map.put(num, 1); } } return map.containsKey(target) ? map.get(target) : 0; } }思路：二分查找 因为nums已经是一个排序数组，所以用二分查找比较好。 所以我们需要找到target的左右边界left、right，分别指向第一个target的左边元素的下标和最后一个target的右边元素的下标。如图所示 具体步骤： （1）左、右指针i、j分别指向数组的首尾； （2）二分查找： 1、当i <= j时跳出； 2、计算中点m = (i + j) / 2; 3、若 nums[m] < target，则 target在闭区间 [m + 1, j] 中，更新i的下标为 i = m + 1； 4、若 nums[m] > target ，则 target在闭区间 [i, m - 1]中，更新j的下标为 j = m - 1； 5、若 nums[m] = target ，则右边界 right在闭区间 [m+1, j] 中；左边界 left在闭区间 [i, m-1]中。因此又分为两种情况： a、若查找右边界right，则执行 i = m + 1 ； b、若查找左边界left，则执行 j = m - 1 ； 6、查找完右边界后，可用 nums[j] = j判断数组中是否包含 target，若不包含则直接提前返回 0 ，无需后续查找左边界。 （3）返回right - left - 1即可。
class Solution { public int search(int[] nums, int target) { int i = 0, j = nums.length - 1; while(i <= j) { int m = (i + j) / 2; if(nums[m] <= target) { i = m + 1; } else { j = m - 1; } } int right = i; if(j >= 0 && nums[j] != target) { return 0; } i = 0; j = nums.length - 1; while(i <= j) { int m = (i + j) / 2; if(nums[m] < target) { i = m + 1; } else { j = m - 1; } } int left = j; return right - left - 1; } }