Data scientists at Amazon are working on a logistics optimization tool to arrange delivery routes based on existing route patterns.
A prototype algorithm takes in two integers, size and target_sum, and generates a sequence of size size whose sum of elements equals target_sum, and the absolute values of the elements form a permutation of size size. The tool outputs the lexicographically smallest such sequence.
Given two integers, size and target_sum, return the lexicographically smallest sequence of integers such that:
- The sum of its elements equals
target_sum. - The absolute values of its elements form a permutation of size
size.
Note: A sequence of size integers is a permutation if it contains the integers from 1 to size exactly once.
Given two permutations x and y, x is lexicographically smaller than y if there exists an index i where x[i] != y[i], and for this smallest index i, x[i] < y[i]. This means that when comparing x and y element by element from the start, the first position at which they differ determines their order. If the element in x is less than the corresponding element in y at this position, x is considered smaller.
Example
Suppose size = 5, target_sum = 9.
Some sequences of size 5 with target_sum = 9 are:
[-1, -2, 3, 4, 5]
[-2, -1, 3, 4, 5]
[-3, 1, 2, 4, 5]
[3, 4, 5, -2, -1]
[-3, 2, 1, 4, 5]Among these, [-3, 1, 2, 4, 5] is lexicographically smallest.
Example
Suppose size = 4, target_sum = -2.
One valid answer is:
[-4, -2, 1, 3]Complete the function findOptimalSequence in the editor below.
The function is expected to return an INTEGER_ARRAY.
The function accepts the following parameters:
INTEGER sizeLONG_INTEGER target_sum
这题的关键是把“绝对值是 1..n 的一个排列”转化成对子集取负号的问题：先从总和 T = 1+2+…+n 出发，若把某些数取负，最终总和会减少这些数的两倍，因此必须满足 (T – target_sum) 为偶数，且需要从 1..n 中选出一组数，其和正好等于 (T – target_sum)/2。为了得到字典序最小序列，通常要优先让前面的数尽量小，所以最终构造时把被选中的数放到负号一侧，并按从大到小贪心选择可行数，再按从小到大输出结果；如果目标和不可能达到，则返回全 0 数组。
