? ? ? ?

????????本題要求在一個已排序的數組 nums 中，找出所有等于目標值 target 的元素下標。若不存在這樣的元素，則返回 {-1, -1}。解決該問題有兩種主要方法：二分查找法和統計計數法。

二分查找法：首先對數組進行排序，然后通過二分查找確定 target 的下界（即第一個大于等于 target 的元素位置）和上界（即最后一個小于等于 target 的元素位置），這兩個位置的交集即為所有等于 target 的元素下標。

? ? ? ? 二分代碼請看34. 在排序數組中查找元素的第一個和最后一個位置——邊界問題不清楚？結果不知道是left還是right？四種大小關系不會轉化？一篇文章告訴你！-CSDN博客

???

????????采用二分查找法：首先確定大于等于目標值的最小索引，再找出小于等于目標值的最大索引，這兩個索引之間的范圍即為等于目標值的區間。

class Solution {
public:int lower_bound(vector<int>& nums,int target) {int n = nums.size();int left = 0,right = n - 1;while (left <= right) {int  mid = (right - left) / 2 + left;if (nums[mid] < target) {left = mid + 1;}else{right = mid - 1;}}return left;}vector<int> targetIndices(vector<int>& nums, int target) {ranges::sort(nums);int n = nums.size();int start = lower_bound(nums,target);if (start == n || nums[start] != target) return {};int end = lower_bound(nums,target + 1) - 1;vector<int> ans;for (int i = start;i <= end;i++){ans.emplace_back(i);}return ans;}
};

? ? ? ? 時間復雜度：O(nlogn)

? ? ? ? 空間復雜度：O(1)? ? ? ?

????????統計小于和等于目標值的方法：通過less_count記錄小于目標值的元素數量，equal_count記錄等于目標值的元素數量。在排序后的數組中，less_count表示第一個目標值的下標，less_count+1表示第二個目標值的下標，依此類推，直到less_count + equal_count - 1。

? ? ? ? 例如：

輸入：nums = [1,2,5,2,3], target = 2
輸出：[1,2]

? ? ?

排序后的數組為 [1, 2, 2, 3, 5]，其中 less = 1，equal = 2，最終結果為 [1, 2]。

class Solution {
public:vector<int> targetIndices(vector<int>& nums, int target) {int less_count = 0,equal_count = 0;for (int it:nums) {if (it < target) less_count++;else if (it == target) equal_count++;}vector<int> ans(equal_count);iota(ans.begin(),ans.end(),less_count);return ans;}
};

? ? ? ? 時間復雜度：O(n)

? ? ? ? 空間復雜度：O(1)