亚马逊OA最优利用问题：空指针排查及算法优化咨询

这是亚马逊OA2019的「最优利用」问题，题目要求：给定两个列表a和b，每个元素是（唯一ID、数值）的整数对，需从a、b各选一个元素，使两者数值之和≤目标值且尽可能接近目标值，返回符合条件的ID对列表；若无符合条件的配对，返回空列表。

我用O(M*N)时间复杂度的Java代码实现了该问题，但部分测试用例会触发NullPointerException，评测平台隐藏了错误行。我已确认：

• foregroundApplications和backgroundApplications列表非空；
• 列表中的元素均为有效整数对，无null元素。

现需找出触发空指针的具体输入案例，同时咨询比O(M*N)更优的解法。

附上我的代码：

public List<List<Integer>> optimize(int deviceCapacity, List<List<Integer>> foregroundApplications, List<List<Integer>> backgroundApplications)
{

TreeMap<Integer, List<List<Integer>>> map = new TreeMap<>();

for(int i = 0; i < foregroundApplications.size(); i++)
{
    for(int j = 0; j < backgroundApplications.size(); j++)
    {
        int sum = foregroundApplications.get(i).get(1) + backgroundApplications.get(j).get(1);
        if(sum<=deviceCapacity)
        {
            List<List<Integer>> list= new ArrayList<>();
            if(map.containsKey(sum))
            {
                list = map.get(sum);
            }
            List<Integer> pair = new ArrayList<>();
            pair.add(foregroundApplications.get(i).get(0));
            pair.add(backgroundApplications.get(j).get(0));
            list.add(pair);
            map.put(sum, list);
        }
    }
}

if(map.size() == 0)
{
    List<List<Integer>> list= new ArrayList<>();
    List<Integer> emptyPair = new ArrayList<>();
    emptyPair.add(null);
    emptyPair.add(null);
    list.add(emptyPair);
    return list;
}


return map.get(map.lastKey());
}

你的代码在无有效配对时，返回的是包含[null, null]的列表，但题目要求此时返回空列表。评测平台在校验返回结果时，若尝试访问这些null元素，就会触发NullPointerException。

比如以下输入案例：

• deviceCapacity = 5
• foregroundApplications = [[1, 6]]
• backgroundApplications = [[2, 7]]

此时所有数值之和（6+7=13）都大于目标值5，map.size()为0，你的代码返回[[null, null]]，平台处理该结果时访问null就会抛出空指针异常。

采用排序+双指针的方法，效率远高于暴力枚举：

1. 分别对foregroundApplications和backgroundApplications按数值从小到大排序；
2. 初始化左指针i在foreground的起始位置，右指针j在background的末尾位置；
3. 记录当前最大的有效和maxSum（初始为-1），以及对应的ID对列表result；
4. 遍历过程：
   • 计算当前和currentSum = foreground.get(i).get(1) + background.get(j).get(1)；
   • 若currentSum <= deviceCapacity：
     • 若currentSum > maxSum：更新maxSum为currentSum，清空result并添加当前ID对；
     • 若currentSum == maxSum：直接将当前ID对加入result；
     • 左移i（尝试更大的和）；
   • 若currentSum > deviceCapacity：右移j（尝试更小的和）；
5. 遍历结束后，若maxSum仍为-1则返回空列表，否则返回result。

该方法的时间复杂度主要来自排序步骤，适用于数据量较大的场景。

内容的提问来源于stack exchange，提问作者grem