每日算法一练：剑指offer——数组篇（6）

1.点名

        某班级 n 位同学的学号为 0 ~ n-1。点名结果记录于升序数组 records。假定仅有一位同学缺席，请返回他的学号。

示例 1:

输入: records = [0,1,2,3,5]
输出: 4

示例 2:

输入: records = [0, 1, 2, 3, 4, 5, 6, 8]
输出: 7

提示：

1 <= records.length <= 10000

1.1二分法查找

        这是一个缺失数问题，在给定的升序数组 records 中找出缺席同学的学号。数组 records 是由班级同学的学号组成的，其中学号从 0 开始，逐个递增，仅有一位同学缺席。要找出缺席的学号，我们可以借助 二分查找 的方法快速定位缺失位置。

解题思路

因为记录是升序的学号列表，仅有一位学号缺失，可以推断：

• 如果数组中没有缺失数字，那么 records[i] 应等于 i（即每个索引位置的值与其索引相等）。
• 如果某个数字缺失，则从缺失位置开始，数组中的元素不再满足 records[i] = i 关系，而是比其索引值大 1。因此，我们可以利用这一规律进行查找。

算法解析

使用二分查找的方式，我们可以在对数时间复杂度 O(log n) 下找到缺失的学号：

1. 初始化左右指针：将 i 设为 0（左指针），j 设为 records.length - 1（右指针），用于二分查找。
2. 循环查找：在 i <= j 的条件下，不断收缩查找范围。
   • 计算中间位置 m = (i + j) / 2。
   • 检查 records[m] 的值：
     • 如果 records[m] == m：说明前面没有缺失元素（当前索引 m 位置的值是正确的），所以缺失的学号在右半部分。将 i 设为 m + 1，向右搜索。
     • 如果 records[m] != m：说明缺失学号在左半部分（从当前 m 位置开始有不匹配的情况）。将 j 设为 m - 1，向左搜索。
3. 结束循环：当 i 大于 j 时，循环结束，缺失的学号即为 i。

最终，i 的位置就是缺失学号的位置。

复杂度分析

• 时间复杂度：二分查找使得时间复杂度为 O(log n)，适用于数据规模较大的情况。
• 空间复杂度：仅使用常数级别的额外空间，空间复杂度为 O(1)。

代码示例：

class Solution {
    public int takeAttendance(int[] records) {
        // 初始化左右指针
        int i = 0, j = records.length - 1;
        
        // 使用二分查找寻找缺失的学号
        while(i <= j) {
            // 计算中间位置 m
            int m = (i + j) / 2;
            
            // 判断中间位置 m 是否与学号对应
            if(records[m] == m) {
                // 如果 records[m] == m，说明左侧都正常匹配，缺失学号在右侧
                i = m + 1; // 将左指针移到右半部分
            } else {
                // 如果 records[m] != m，说明缺失学号在左半部分
                j = m - 1; // 将右指针移到左半部分
            }
        }
        
        // 最终 i 的位置即为缺失的学号
        return i;
    }
}

2.查找总价值为目标值的两个商品

        购物车内的商品价格按照升序记录于数组 price。请在购物车中找到两个商品的价格总和刚好是 target。若存在多种情况，返回任一结果即可。

示例 1：

输入：price = [3, 9, 12, 15], target = 18
输出：[3,15] 或者 [15,3]

示例 2：

输入：price = [8, 21, 27, 34, 52, 66], target = 61
输出：[27,34] 或者 [34,27]

提示：

• 1 <= price.length <= 10^5
• 1 <= price[i] <= 10^6
• 1 <= target <= 2*10^6

2.1双指针检索

这是一个典型的双指针问题，因为数组 price 已经是升序排列，所以可以使用双指针快速查找两个数的和为 target 的组合。下面是解题思路、算法流程及复杂度分析。

解题思路

1. 双指针：从数组的两端开始，逐步缩小范围，利用排序数组的特性进行查找。

   • 若两个指针指向的元素之和小于 target，则需要更大的和，因此将左指针右移。
   • 若和大于 target，则需要更小的和，因此将右指针左移。
   • 当和等于 target 时，找到解。

2. 提前返回：找到符合条件的两个数后，立即返回结果数组 [price[i], price[j]]，这样可以保证时间效率。

算法解析

1. 初始化：定义两个指针 i 和 j，分别指向数组的首尾位置。
2. 循环条件：在 i < j 的条件下进行迭代：
   • 计算 price[i] + price[j] 的和 s。
   • 比较 s 和 target：
     • 如果 s == target，返回 [price[i], price[j]]。
     • 如果 s < target，左指针 i 右移，增加和的值。
     • 如果 s > target，右指针 j 左移，减小和的值。
3. 返回结果：若循环结束仍未找到，则返回空数组 []。

复杂度分析

• 时间复杂度：O(N)，其中 N 为数组 price 的长度。双指针仅需线性遍历一次数组。
• 空间复杂度：O(1)，仅使用了常数级的额外空间。

代码示例：

class Solution {
    public int[] twoSum(int[] price, int target) {
        // 初始化左右指针
        int i = 0, j = price.length - 1;
        
        // 使用双指针查找两个和为 target 的数
        while (i < j) {
            // 计算当前左右指针指向元素的和
            int s = price[i] + price[j];
            
            // 判断当前和 s 是否等于目标 target
            if (s < target) {
                // 若 s 小于 target，说明和偏小，需要增大和
                // 将左指针右移
                i++;
            } else if (s > target) {
                // 若 s 大于 target，说明和偏大，需要减小和
                // 将右指针左移
                j--;
            } else {
                // 若 s 等于 target，找到符合条件的组合，立即返回
                return new int[] { price[i], price[j] };
            }
        }
        
        // 若未找到符合条件的组合，返回空数组
        return new int[0];
    }
}

3.文件组合

        待传输文件被切分成多个部分，按照原排列顺序，每部分文件编号均为一个 正整数（至少含有两个文件）。传输要求为：连续文件编号总和为接收方指定数字 target 的所有文件。请返回所有符合该要求的文件传输组合列表。

注意，返回时需遵循以下规则：

• 每种组合按照文件编号 升序 排列；
• 不同组合按照第一个文件编号 升序 排列。

示例 1：

输入：target = 12
输出：[[3, 4, 5]]
解释：在上述示例中，存在一个连续正整数序列的和为 12，为 [3, 4, 5]。

示例 2：

输入：target = 18
输出：[[3,4,5,6],[5,6,7]]
解释：在上述示例中，存在两个连续正整数序列的和分别为 18，分别为 [3, 4, 5, 6] 和 [5, 6, 7]。

提示：

• 1 <= target <= 10^5

3.1滑动窗口

        这是一个寻找连续正整数序列的和等于指定目标值 target 的问题。我们可以使用双指针滑动窗口的方法来高效地查找所有符合条件的组合。下面是解题思路、算法流程和复杂度分析。

解题思路

1. 双指针法：使用两个指针 i 和 j 来表示当前正在考虑的连续正整数的起始和结束位置。
2. 序列和的计算：维护一个当前和 s，初始为 3（即 1 + 2），表示 i=1 和 j=2 的和。
3. 遍历和调整：
   • 如果当前和 s 等于目标 target，则记录下当前的连续整数序列。
   • 如果当前和 s 大于或等于目标 target，则通过移动左指针 i 来减小和。
   • 如果当前和 s 小于目标 target，则通过移动右指针 j 来增大和。

算法流程

1. 初始化：

   • i 为 1，表示当前序列的起始位置。
   • j 为 2，表示当前序列的结束位置。
   • s 为 3，即 i 和 j 所指元素的和。
   • 使用一个列表 res 来存储符合条件的组合。

2. 双指针循环：

   • 当 i 小于 j 时进行循环：
     • 如果 s 等于 target，记录下从 i 到 j 的连续整数。
     • 如果 s 大于或等于 target，将 s 减去 i 并将 i 右移。
     • 如果 s 小于 target，将 j 右移，并更新 s。

3. 返回结果：

   • 将列表 res 转换为二维数组返回。

复杂度分析

• 时间复杂度：O(N)，其中 N 是目标 target 的值。双指针会遍历连续的正整数并调整，整体复杂度为线性。
• 空间复杂度：O(M)，其中 M 是存储符合条件组合的个数。由于使用了额外的列表来存储结果，空间复杂度为线性。

import java.util.ArrayList;
import java.util.List;

class Solution {
    public int[][] fileCombination(int target) {
        // 初始化双指针
        int i = 1, j = 2, s = 3; // s 为当前连续正整数和
        List<int[]> res = new ArrayList<>(); // 存储结果
        
        // 双指针查找
        while (i < j) {
            if (s == target) {
                // 找到符合条件的组合，记录下当前的连续正整数
                int[] ans = new int[j - i + 1];
                for (int k = i; k <= j; k++)
                    ans[k - i] = k; // 填充组合
                res.add(ans); // 添加到结果列表
            }
            // 调整指针
            if (s >= target) {
                s -= i; // 减去左边的数字
                i++; // 左指针右移
            } else {
                j++; // 右指针右移
                s += j; // 增加右边的数字
            }
        }
        
        // 返回结果数组
        return res.toArray(new int[0][]);
    }
}