LCP18.早餐组合

题目

！传送门题目太长就不描述了

解题思路

双指针（最好理解），对向双指针，取一个数组做完全遍历，关键步骤的思路在注释中。

代码

class Solution {
    public int breakfastNumber(int[] staple, int[] drinks, int x) {
        int ps = 0, pd = drinks.length - 1, count = 0;
        Arrays.sort(staple);
        Arrays.sort(drinks);
        while (ps < staple.length && pd >= 0) {
             if (staple[ps] + drinks[pd] <= x) {
                count += pd + 1;//这里满足条件之后，此处之前的左右元素都满足条件，因为是有序的。
                count = count % 1000000007;
                ps++;//staple左侧指针向前推进一个，直至全部遍历完staple数组。
            } else {//如果超出规定则drink数组右侧指针向前推进一个。
                pd--;
            }
        }
        return count;
    }
}