2670. Find the Distinct Difference Array 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
    public int[] distinctDifferenceArray(int[] nums) {
        int[] prefix = new int[nums.length];
        int[] suffix = new int[nums.length];

        Set<Integer> prefixSet = new HashSet<>();
        Set<Integer> suffixSet = new HashSet<>();
        prefixSet.add(nums[0]);
        suffixSet.add(nums[nums.length - 1]);
        prefix[0] = prefixSet.size();
        suffix[suffix.length - 1] = suffixSet.size();

        for (int i = 1; i < nums.length; i++) {
            prefixSet.add(nums[i]);
            prefix[i] = prefixSet.size();
            suffixSet.add(nums[nums.length - 1 - i]);
            suffix[nums.length - 1 - i] = suffixSet.size();
        }

        int[] diff = new int[nums.length];
        for (int i = 0; i < diff.length; i++) {
            diff[i] = prefix[i] - (i + 1 < suffix.length ? suffix[i + 1] : 0);
        }
        return diff;
    }
}

若正序与逆序在一个 for 循环中遍历，则需要注意数组的索引。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int[] distinctDifferenceArray(int[] nums) {
        int[] suffix = new int[nums.length + 1]; // 加一是为了避免后续单独处理可能越界的索引
        Set<Integer> set = new HashSet<>();
        for (int i = nums.length - 1; i > 0; i--) {
            set.add(nums[i]);
            suffix[i] = set.size();
        }

        set.clear();
        int[] diff = new int[nums.length];
        for (int i = 0; i < diff.length; i++) {
            set.add(nums[i]);
            diff[i] = set.size() - suffix[i + 1];
        }
        return diff;
    }
}

References

2670. Find the Distinct Difference Array