薪资流水虚报被开除？聊聊双指针算法与有序转化数组题解

最近在网上看到一个挺有代表性的职场帖子。一位求职者在面试时夸大了自己的薪资水平，声称月薪两万五，期望薪资要到三万，公司也爽快地给了Offer。结果入职后，HR催要薪资流水，他发去的个税截图却显示实际月薪还不到一万。

说实话，求职时适当优化一下自己的经历和期望，大家或多或少都能理解。但这种直接从“不到一万”吹到“两万五”的跨度，确实有点过猛了。公司现在抓住“薪资流水不符”这个理由不放，要求取消录用，一方面是基于事实，另一方面恐怕也是觉得后续管理上会埋下隐患。

至于当事人想争取的“2N”赔偿，在实际仲裁中真没那么简单，关键还得看具体的入职流程、证据材料以及公司的辞退理由是否充分合法。打工不易，但在面试求职和谈薪阶段，有些“牛”吹得比KPI目标还高，风险着实不小。

聊完这个现实案例，我们切换一下频道，来看一道与之风格迥异但同样考验思路的算法/数据结构面试题。

面试题：有序转化数组

题目要求很明确：给你一个有序数组 nums，以及三个整数参数 a, b, c。你需要将数组中的每个元素 x 代入二次函数 f(x) = ax^2 + bx + c 进行计算，最终返回一个仍然保持有序的新数组。

很多人的第一反应是：这还不简单？先遍历计算，再用 Arrays.sort() 排个序不就搞定了？

这么做当然可以，但题目显然不是想考察你调用库函数的能力。原数组已经有序，这个信息非常宝贵，直接排序的 O(n log n) 解法浪费了这个条件。

我们先看看最直接的实现：

public int[] sortTransformedArray(int[] nums, int a, int b, int c) {
    int[] ans = new int[nums.length];
    for (int i = 0; i < nums.length; i++) {
        ans[i] = calc(nums[i], a, b, c);
    }
    Arrays.sort(ans);
    return ans;
}

private int calc(int x, int a, int b, int c) {
    return a * x * x + b * x + c;
}

这个写法没问题，但时间复杂度的瓶颈在最后的排序上。优化的关键在于理解二次函数的图像特性。

当 a > 0 时，抛物线开口向上，函数值在两端较大，中间较小。
当 a < 0 时，抛物线开口向下，函数值在两端较小，中间较大。

换句话说，无论开口方向如何，原数组两端的元素经过函数计算后，其值往往比中间的元素更“极端”。这个特性让我们有机会使用双指针，在 O(n) 的时间内完成排序。

思路是：设置左指针 l 和右指针 r，分别指向原数组的头尾。每次比较 f(nums[l]) 和 f(nums[r])，根据 a 的正负决定将哪个值填入结果数组的相应位置。

下面是核心的实现代码：

public int[] sortTransformedArray(int[] nums, int a, int b, int c) {
    int n = nums.length;
    int[] ans = new int[n];
    int l = 0, r = n - 1;
    int idx = a >= 0 ? n - 1 : 0;

    while (l <= r) {
        int left = calc(nums[l], a, b, c);
        int right = calc(nums[r], a, b, c);

        if (a >= 0) {
            if (left > right) {
                ans[idx--] = left;
                l++;
            } else {
                ans[idx--] = right;
                r--;
            }
        } else {
            if (left < right) {
                ans[idx++] = left;
                l++;
            } else {
                ans[idx++] = right;
                r--;
            }
        }
    }
    return ans;
}

private int calc(int x, int a, int b, int c) {
    return a * x * x + b * x + c;
}

这段Java代码的精髓不在于“双指针”这个名词，而在于结果数组的填充方向：

• a >= 0：较大的值会出现在转化后数组的两端，所以我们应该从结果数组的尾部开始向前填充。
• a < 0：较小的值会出现在转化后数组的两端，所以我们应该从结果数组的头部开始向后填充。

举个例子，用 nums = [-4,-2,2,4], a = 1, b = 3, c = 5 来跑一下：

f(-4)= 9
f(-2)= 3
f(2) = 15
f(4) = 33

最终得到的有序数组是 [3, 9, 15, 33]。你会发现，原数组虽有序，但经过函数映射后并非天然有序。真正高效的解法不是重新排序，而是利用抛物线“两端更极端”的特征，一边计算，一边决定放入的位置。

这类题目在面试中很典型。它不依赖复杂的技巧，代码量也不大，但能有效区分候选人是在机械套用模板，还是真正理解了问题背后的数学本质（从公式到图像），并能将这种理解转化为清晰的代码逻辑（指针的移动规则）。

无论是处理职场中诚信与技巧的平衡，还是攻克一道精巧的算法题，核心都在于对底层逻辑的把握。希望今天的分享对你有用。如果你对更多算法/数据结构的解题思路或面试求职的实战经验感兴趣，欢迎来云栈社区和我们一起交流探讨。