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

这道题到底在问什么

输入

nums=[1,2,5,2,3], target=2

输出

[1,2] 排序后 [1,2,2,3,5],值 2 在下标 1 和 2

输入

nums=[1,2,5,2,3], target=4

输出

[] 数组里没有 4

最优解：一步一步想明白

1. 3记住这套路:先排序让相等的值抱团,再扫一遍把等于 target 的下标一个个收进来。下面先看原始数组长什么样。
2. 4这是原始的 nums,一共 8 个数,还没排序。我们要找的目标值是 3。你先扫一眼,3 在这里东一个西一个,毫无规律,直接在原数组上找下标是没有意义的,因为题目要的是排序之后的下标。
3. 5把原数组里所有值为 3 的格子标成绿色,它们分别在下标 1、3、5。你看,它们是散开的,中间还夹着别的数。这正是为什么要先排序:排完之后,这三个 3 会被拢到一起。
4. 6调用语言内置的排序,把 nums 从小到大排好,现在它是 [1,3,3,3,5,6,8,9]。注意看,三个 3 已经紧紧挨在一块了。接下来从下标 0 开始,一格一格往右扫,遇到等于 3 的就把下标收进答案。
5. 7紫色指针走到下标 0,这里的值是 1。拿它和 target 也就是 3 比一比,看是小、是等还是大。
6. 81 比 3 小,它排在目标块的左边,不是我们要的,标成蓝色跳过。继续往右走。
7. 9紫色指针走到下标 1,这里的值是 3。拿它和 target 也就是 3 比一比,看是小、是等还是大。
8. 10正好等于 3,命中!把下标 1 收进答案,这一格标成绿色。目前收集到 [1]。
9. 11紫色指针走到下标 2,这里的值是 3。拿它和 target 也就是 3 比一比,看是小、是等还是大。
10. 12正好等于 3,命中!把下标 2 收进答案,这一格标成绿色。目前收集到 [1,2]。
11. 13紫色指针走到下标 3,这里的值是 3。拿它和 target 也就是 3 比一比,看是小、是等还是大。
12. 14正好等于 3,命中!把下标 3 收进答案,这一格标成绿色。目前收集到 [1,2,3]。
13. 15紫色指针走到下标 4,这里的值是 5。拿它和 target 也就是 3 比一比,看是小、是等还是大。
14. 165 比 3 大了。因为已经排好序,它右边的数只会更大,再也不会碰到 3,这一格标灰。参考代码是老实扫完的,但你心里要清楚:到这里其实已经可以收工了。
15. 17紫色指针走到下标 5,这里的值是 6。拿它和 target 也就是 3 比一比,看是小、是等还是大。
16. 186 比 3 大了。因为已经排好序,它右边的数只会更大,再也不会碰到 3,这一格标灰。参考代码是老实扫完的,但你心里要清楚:到这里其实已经可以收工了。
17. 19紫色指针走到下标 6,这里的值是 8。拿它和 target 也就是 3 比一比,看是小、是等还是大。
18. 208 比 3 大了。因为已经排好序,它右边的数只会更大,再也不会碰到 3,这一格标灰。参考代码是老实扫完的,但你心里要清楚:到这里其实已经可以收工了。
19. 21紫色指针走到下标 7,这里的值是 9。拿它和 target 也就是 3 比一比,看是小、是等还是大。
20. 229 比 3 大了。因为已经排好序,它右边的数只会更大,再也不会碰到 3,这一格标灰。参考代码是老实扫完的,但你心里要清楚:到这里其实已经可以收工了。
21. 23这里藏着一个更快的思路。比 3 小的元素只有 1 个,就是那个 1,所以排序后第一个 3 一定落在下标 1。目标块从下标 1 起头,一共 3 个 3,于是下标就是 1、2、3。顺着这个观察,其实连排序都能省掉,后面面试环节细说。
22. 24扫完全程,绿色的三格就是等于 3 的位置,下标依次是 1、2、3。所以答案是 [1,2,3],和我们一开始说的对上了。左边蓝色的更小、右边灰色的更大,绿色这一块就是目标下标。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

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]

#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;
    }
};

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;
    }
}

复杂度

面试官可能追问