找出数组排序后的目标下标 图解题解

排序之后再找下标，这题到底要返回哪些位置

给一个下标从 0 开始的整数数组 nums 和目标值 target，先把 nums 按非递减（从小到大、允许相等）排好，再返回排序后所有等于 target 的元素所在的下标，按递增排列；一个都没有就返回空列表。题面 nums=[1,2,5,2,3]、target=2 排完是 [1,2,2,3,5]，两个 2 落在下标 1 和 2，答案 [1,2]；换成 target=4，数组里没有 4，返回空列表 []。

在原数组上直接记下标，为什么整个答案都是错的

最容易踩的一步，是拿到 target 就在原数组里数它出现在哪几个下标、直接返回。可题目要的是排序之后的下标：原数组 [1,2,5,2,3] 里两个 2 待在下标 1 和 3，一排序变成 [1,2,2,3,5]，这两个 2 却落到了下标 1 和 2——位置整个挪了。排序前的下标和排序后的下标是两码事，不先排就找，答对纯属碰巧。

排完序之后，相同的值为什么一定连成一段

非递减排序把元素从小到大摆好，等于 target 的那些值大小完全一样，排序时既不会插到比它小的前头、也不会窜到比它大的后头，只能彼此紧挨、连成一整块连续下标。既然它们抱成一团，就用不着东找西找：从下标 0 一路扫到末尾，碰到等于 target 的就把当前下标收进结果，先扫到的下标天然更小，收出来正好是递增顺序。

参考代码就是这两下：nums.sort() 原地排完，再用一句列表推导 [i for i, v in enumerate(nums) if v == target]，把命中的下标全数收下。

排序加一遍扫描，具体是怎么走完的

第一步原地排序，把 nums 变成非递减序列。第二步从左到右扫，用下标 i 遍历每个元素 v：v 等于 target 就记下这个 i；v 小于 target 说明还没扫进目标块、继续往右；v 大于 target 说明已经越过目标块（后面只会更大），剩下的也都不是。扫到头，收集起来的下标列表就是答案；如果一路下来没有一个等于 target，列表始终是空的，直接返回空列表。

拿题面 [1,2,5,2,3]、target=2 亲手走一遍

先排序：[1,2,5,2,3] 变成 [1,2,2,3,5]。再从头往右扫：下标 0 处是 1，比 2 小，跳过；下标 1、2 处都是 2，正好命中，依次收下下标 1 和 2，结果攒成 [1,2]；下标 3 处是 3、下标 4 处是 5，都比 2 大、越过了目标块，跳过。扫完返回 [1,2]，和题面对上。若把 target 换成 4，整趟没有一个等于 4，返回空列表 []。

复杂度卡在排序，还有哪两处收尾容易写反

时间上排序是 O(n log n) 的主导项，后面收集下标只扫一遍是 O(n)，合起来仍是 O(n log n)；空间除去输出列表只用常数个变量，不计排序内部开销是 O(1)。收尾两处别写反：target 不存在时要返回空列表 []，别返回 [-1] 或抛错，题面白纸黑字要的就是空列表；重复的 target 有几个就得收几个下标，别以为相同值只算一个，题面里两个 2 就对应下标 1、2，漏一个答案就短一截。

Python

from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
class Solution:
    def targetIndices(self, nums: List[int], target: int) -> List[int]:
        nums.sort()
        return [i for i, v in enumerate(nums) if v == target]

C++

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
class Solution {
public:
    vector<int> targetIndices(vector<int>& nums, int target) {
        sort(nums.begin(), nums.end());
        vector<int> ans;
        for (int i = 0; i < nums.size(); ++i) {
            if (nums[i] == target) {
                ans.push_back(i);
            }
        }
        return ans;
    }
};

Java

import java.util.*;
class Solution {
    public List<Integer> targetIndices(int[] nums, int target) {
        Arrays.sort(nums);
        List<Integer> ans = new ArrayList<>();
        for (int i = 0; i < nums.length; ++i) {
            if (nums[i] == target) {
                ans.add(i);
            }
        }
        return ans;
    }
}