优选算法 - 2 （ 二分查找 && 前缀和 6000 字详解 ）

一： 二分查找

1.1 ⼆分查找

题目链接：二分查找

class Solution {
    public int search(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while(left <= right){
            //防溢出，每次循环都要动态更新这个中点
            int mid = left + (right - left) / 2;
            
            //大了，往小的地方找
            if(nums[mid] > target) right = mid - 1;
            //小了，往大的地方找
            else if(nums[mid] < target) left = mid + 1;
            else return mid;
        }
        return -1;
             
    }
}

1.2 在排序数组中查找元素的第⼀个和最后⼀个位置

题目链接：在排序数组中查找元素的第⼀个和最后⼀个位置

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int left = 0, right = nums.length - 1, mid = 0;
        //先处理特殊情况
        int[] ret = new int[2];
        ret[0] = -1; ret[1] = -1;
        if(nums.length == 0) return ret;

        //寻找左端点
        while(left < right){
            mid = left + (right - left) / 2;
            if(nums[mid] < target) left = mid + 1;
            else right = mid;
        }
        //循环结束后 left 和 right 相遇，如果相遇的值和 target 相同，说明这个数组是有左端点
        if(nums[left] == target) ret[0] = left;
        else return ret;

        //寻找右端点,寻找前需要把左右指针重置一下
        left = 0; right = nums.length - 1;
        while(left < right){
            mid = left + (right - left + 1) / 2;
            if(nums[mid] <= target) left = mid;
            else right = mid - 1;
        }
        //此时就不用判断相遇值是否和 target 相同了，左端点时已经判断过了
        ret[1] = right;
        return ret;
        
    }
}

1.3 搜索插入位置

题目链接：搜索插入位置

class Solution {
    public int searchInsert(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while(left < right){
            int mid = left + (right - left) / 2;
            if(nums[mid] < target)  left = mid + 1;
            else right = mid;
        }
        
        //处理一下特殊情况，即把数字插入最后一个位置
        if(nums[left] < target) return left + 1;
        return left;
    }
}

1.4 x 的平方根

题目链接：x 的平方根

class Solution {
    public int mySqrt(int x) {
        long left = 1, right = x;
        if(x < 1) return 0;
        while(left < right){    
            long mid = left + (right - left + 1) / 2;
            if(mid * mid <= x) left = mid;
            else right = mid - 1;
        }
        return (int)left;
    }
}

1.5 山峰数组的峰顶

题目链接：山峰数组的峰顶

class Solution {
    public int peakIndexInMountainArray(int[] arr) {
        //山峰一定不可能在数组的左右边界
        int left = 1, right = arr.length - 2;
        while(left < right){
            int mid = left + (right - left + 1) / 2;
            if(arr[mid] > arr[mid - 1]) left = mid;
            else right = mid - 1;
        }
        //循环结束后 left 和 right 相遇，相遇的值就是峰顶
        return left;
    }
}

1.6 寻找峰值

题目链接： 寻找峰值

class Solution {
    public int findPeakElement(int[] nums) {
        int left = 0, right = nums.length - 1;
        while(left <  right){
            int mid  = left +(right - left) / 2;
            if(nums[mid] < nums[mid + 1]) left = mid + 1;
            else right = mid;
        }
        //循环结束后，两指针相遇，两个指针都存储着一个峰值
        return left;
        
    }
}

1.7 搜索旋转排序数组中的最小值

题目链接：搜索旋转排序数组中的最小值

class Solution {
    public int findMin(int[] nums) {
        int left = 0, right = nums.length - 1;
        while(left < right){
            int mid = left + (right - left) / 2;
            if(nums[mid] > nums[right]) left = mid + 1;
            else right = mid;
        }
        return nums[left];

    }
}

1.8 点名

题目链接：点名

class Solution {
    public int takeAttendance(int[] records) {
    int left = 0, right = records.length;
    while(left < right){
        int mid = left + (right - left) / 2;
        if(records[mid] == mid) left = mid + 1;
        else right = mid;
    }      
    //处理一下特殊情况，防止却的是数组的最后一位
    if(left < records.length && records[left] == left) return records.length;
    else return left;
    }
} 

二：前缀和

1.1 一维前缀和

题目链接：前缀和一维前缀和

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        //先处理数据，number_count 是输入数字的个数，line 代表要输出多少行
        int number_count = in.nextInt(), line = in.nextInt();
        int[] arr = new int[number_count + 1];
        for(int i = 1; i <= number_count; i++) arr[i] = in.nextInt();

        //接着处理一下 dp 数组,因为数据比较大，用 long 类型防溢出
        long[] dp = new long[number_count + 1];
        for(int i = 1; i <= number_count; i++) dp[i] = dp[i - 1] + arr[i];

        while(line > 0){
            int left = in.nextInt(), right = in.nextInt();
            System.out.println(dp[right] - dp[left - 1]);
            line--;
        }
    }
}

1.2 二维前缀和

题目链接：前缀和二维前缀和

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        //先读取数据
        int n = in.nextInt(), m = in.nextInt(), q = in.nextInt();
        int[][] arr = new int[n + 1][m + 1];
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= m; j++)
                arr[i][j] = in.nextInt();

        //接下来预处理一个前缀和矩阵,long 是为了防溢出
        long[][] dp = new long[n + 1][m + 1];
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= m; j++)
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1] + arr[i][j] - dp[i - 1][j - 1];

        //接下来正式操作
        while(q > 0){
            int x1 = in.nextInt(), y1 = in.nextInt(), x2 = in.nextInt(), y2 = in.nextInt();
            System.out.println(dp[x2][y2] - dp[x1 - 1][y2] - dp[x2][y1 - 1] + dp[x1 - 1][y1 - 1]);            q--;
        }
    }
}

1.3 查找数组的中心下标

题目链接：查找数组的中心下标

class Solution {
    public int pivotIndex(int[] nums) {
        int n = nums.length;
        int[] f = new int[n];
        int[] g = new int[n];
        // 接着初始化前缀和数组和后缀和数组，因为 f[0] 和 g[0] 本来就为 0，此时跳过 0 下标
        for (int i = 1; i < n; i++) 
            f[i] = f[i - 1] + nums[i - 1];
        
        for (int i = n - 2; i >= 0; i--) 
            g[i] = g[i + 1] + nums[i + 1];

        for (int i = 0; i < n; i++) 
            if (f[i] == g[i]) return i;

        return -1;
    }
}

1.4 除自身以外数组的乘积

题目链接：除自身以外数组的乘积

class Solution {
    public int[] productExceptSelf(int[] nums) {
        //利用前缀积和后缀积的思想解决问题
        int n = nums.length;
        int[] f = new int[n];
        int[] g = new int[n];

        f[0] = g[n - 1] = 1;
        for(int i = 1; i < n; i++) 
            f[i] = f[i - 1] * nums[i - 1];
        for(int i = n - 2; i >= 0; i--)
            g[i] = g[i + 1] * nums[i + 1];

        //接着使用预处理的前缀和后缀数组
        int[] ret = new int[n];
        for(int i = 0; i < n; i ++)
            ret[i] = f[i] * g[i];

        return ret;

    }
}

1.5 和为 K 的子数组

题目链接：和为 K 的子数组

class Solution {
   public int subarraySum(int[] nums, int k) {
    //用哈希表存储数组的前缀和的值以及这个前缀和出现的次数
    Map<Integer, Integer> hash = new HashMap<Integer, Integer>();
    //用 sum 来记录前缀和的值，用 ret 存储和为 k 子数组的个数
    int sum = 0, ret = 0;
    //处理一个特殊的情况, 当整个数组的和才为 k 时，我们需要从哈希表中找值为 0 的前缀和，如果不处理的话就回去 [0， -1] 去找和为 sum - k 的数组，这明显不存在
     hash.put(0, 1);

    //接着开始遍历数组的每一个元素
    for(int x : nums){
        sum += x;
        //判断一下哈希表是否存储有 和为 sum - k 的前缀和，如果有，说明存在有一个和为 k 的子数组的个数 ， ret += 上这个前缀和的次数
        ret += hash.getOrDefault(sum - k, 0);
        //接着在每一次的遍历中把前缀和的值存储在哈希表中，如果已经存在，则在原来的次数上 + 1
        hash.put(sum, hash.getOrDefault(sum, 0) + 1);           
    }
   
   //遍历完成后，ret 存储的就是和为 k 子数组的个数
   return ret;
}

}

1.6 和可被 K 整除的子数组

题目链接：和可被 K 整除的子数组

class Solution {
    public int subarraysDivByK(int[] nums, int k) {
        // 创建一个哈希表，用于存储前缀和的模 k 结果及其出现的次数
        Map<Integer, Integer> hash = new HashMap<>();
        
        // 初始化哈希表：前缀和为 0 的情况，模 k 的结果为 0，表示有一个前缀和为 0 的子数组
        // 这是为了处理直接从数组开头开始的子数组可以被 k 整除的情况
        hash.put(0, 1);

        int sum = 0; // 定义变量 sum 用于记录当前的前缀和
        int ret = 0; // 定义变量 ret 用于记录满足条件的子数组的个数

        // 遍历数组中的每一个元素
        for (int x : nums) {
            sum += x; // 累加当前元素到前缀和 sum
            
            // 计算当前前缀和 sum 对 k 的余数（并进行修正以保证是非负数）
            // 如果 sum 是负数，直接对 k 取模会得到负数，因此使用 (sum % k + k) % k 来确保结果为非负
            int r = (sum % k + k) % k;

            // 检查当前余数 r 是否已经在哈希表中出现过
            // 如果出现过，则表示存在一个子数组的和能被 k 整除
            // 因为前缀和的余数相同意味着两者之差可以被 k 整除
            ret += hash.getOrDefault(r, 0);

            // 将当前余数 r 存入哈希表，若已存在则增加出现次数
            hash.put(r, hash.getOrDefault(r, 0) + 1);
        }

        // 返回满足条件的子数组的数量
        return ret;
    }
}

1.7 连续数组

题目链接：连续数组

class Solution {
    public int findMaxLength(int[] nums) {
        //用哈希表存储前缀和的值以及最早出现这个前缀和的位置
        Map<Integer,Integer> hash = new HashMap<>();
        //用 ret 存储最长子数组的长度，sum 前缀和的值
        int ret = 0;
        int sum = 0;

        //先处理一下边界情况，防止从数组开头就可以达到平衡的情况
        hash.put(0, -1);
        //接着开始正式操作，遍历数组的每一个元素
        for(int i = 0; i < nums.length; i++){
            //先把前缀和 sum 求出来,因为我们是模拟的，当元素为 0 时，我们 -1 即可，如果是 1 就正常加一
            sum += (nums[i] == 0 ? -1 : 1);
            //接着判断一下哈希表中是否有 sum ，如果在当前索引中，在哈希表找到了 sum 的键，说明这是一个平衡的数组，如果没出现就正常把没出现过的前缀和放入哈希表中
            if(hash.containsKey(sum)) ret = Math.max(ret, i - hash.get(sum));
            else hash.put(sum, i);
        }

        return ret;
    }
}

1.8 矩形区域和

题目链接：矩形区域和

在这里插入图片描述

class Solution {
    public int[][] matrixBlockSum(int[][] mat, int k) {
        //先获取数组的行数 m 和列数 n
        int m = mat.length, n = mat[0].length;
        //接着定义一个二维前缀和数组 dp，并对 dp 进行初始化,因为 dp 是从 1 开始计数的，所以我们多开辟一行一列
        int[][] dp = new int[m + 1][n + 1];
        for(int i = 1; i <= m; i++)
            for(int j = 1; j <= n; j++)
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] + mat[i - 1][j - 1];

        //初始化完 dp 后开始处理 ret，ret 用于存储结果矩阵
        int[][] ret = new int[m][n];
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                // (x1, y1) 是矩形区域左上角，(x2, y2) 是矩形区域右下角
                int x1 = Math.max(0, i - k) + 1;
                int y1 = Math.max(0, j - k) + 1;
                int x2 = Math.min(m - 1, i + k) + 1;
                int y2 = Math.min(n - 1, j + k) + 1;

                ret[i][j] =  dp[x2][y2] - dp[x1 - 1][y2] - dp[x2][y1 - 1] + dp[x1 - 1][y1 - 1];
            }
        }

        return ret;         
    }
}