Optimal Utilization Solution

Optimal Utilization

给定两个列表a和b，每个列表都是由若干个整数对组成，第一个整数表示id，第二个整数表示值。

分别从a和b各取一个元素（整数对）使得值的和小于等于且尽可能接近于目标值，找出所有这样的组合并且返回他们的id

题面中是两个数的和等于或接近于某一个目标值，一般都是双指针题，按值排序后，一个指针指向头，一个指针指向尾，然后根据大小关系移动。

本题有个关键点，也是很多题解忽视了的，就是要找到所有的满足条件的组合，那么当目前两个指针指向的元素值小于或等于目标值时，不能算完当前就将左指针往右移动了，而是应该考虑到右指针指向的值在左边是否有重复值，需要遍历这些重复值，否则会漏。
比如：

1
2
3

a = {{1, 5}, {2, 7}};
b = {{2, 4}, {3, 4}};
target = 10;

当左指针i=0, 右指针j=1时，此时和为9小于10，得到一对{1, 3}，所以应该是左指针向右，但是如果这里不去考虑右指针重复值，就会错失一对答案{1, 2}

另外，如果本题去除小于等于目标值，而是只是尽可能接近于目标值，那么也就是大于等于和小于等于两端接近，这时候还需要考虑左指针指向的值是否有重复了。

本题代码

public static List<int[]> getPairs(int[][] a, int[][] b, int target) {
    Arrays.sort(a, Comparator.comparingInt(x -> x[1]));
    Arrays.sort(b, Comparator.comparingInt(x -> x[1]));
    List<int[]> ans = new ArrayList<>();
    int n = a.length;
    int m = b.length;
    int i = 0, j = m-1;
    int max = Integer.MIN_VALUE;
    while (i < n && j >= 0) {
        int sum = a[i][1] + b[j][1];
        // 比target大，要减小和，右指针向左移
        if (sum > target) {
            --j;
        }
        else {
            if (max <= sum) {
                // 如果找到了更大的sum，那么前面存储的都无效了，更新最大值并清除
                if (max < sum) {
                    max = sum;
                    ans.clear();
                }
                ans.add(new int[]{a[i][0], b[j][0]});
                int idx = j-1;
                // 重复值都加入
                while (idx >= 0 && b[idx][1] == b[idx+1][1]) {
                    ans.add(new int[]{a[i][0], b[idx--][0]});
                }
            }
            ++i;
        }
    }
    return ans;
}