01.Array（数组）

0、基础理论

1、二分查找

给定一个包含 n 个元素，有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

使用二分查找的条件：数组为有序数组，且数组中无重复元素；因为一旦有重复元素，使用二分查找法返回的元素下标可能不是唯一的。

1.1、方法一（左闭右闭）

定义 target 是在一个在左闭右闭的区间里，也就是[left, right]，则：

while (left <= right) 要使用 <= ，因为 left == right 是有意义的，所以使用 <=
if (nums[middle] > target) right 要赋值为 middle - 1，因为当前这个 nums[middle]一定不是 target，那么接下来要查找的左区间结束下标位置就是 middle - 1

    public static int binarySearch1(int[] nums, int target) {
        int idxL = 0;
        int idxR = nums.length - 1; // 定义target在左闭右闭的区间里 [left, right]
        int idxM;
        while (idxL <= idxR) { // 当left==right，区间[left, right]依然有效，所以用 <=
            idxM = (idxL + idxR) / 2;
            if (nums[idxM] < target) {
                idxL = idxM + 1; // target 在右区间，所以[middle + 1, right]
            } else if (nums[idxM] > target) {
                idxR = idxM - 1; // target 在左区间，所以[left, middle - 1]
            } else {
                return idxM;
            }
        }
        return -1; // 未找到目标值
    }

1.2、方法二（左闭右开）

定义 target 是在一个在左闭右开的区间里，也就是[left, right)，则：

while (left < right)，这里使用 < ,因为 left == right 在区间[left, right)是没有意义的
if (nums[middle] > target) right 更新为 middle，因为当前 nums[middle]不等于 target，去左区间继续寻找，而寻找区间是左闭右开区间，所以 right 更新为 middle，即：下一个查询区间不会去比较 nums[middle]

    public static int binarySearch2(int[] nums, int target) {
        int idxL = 0;
        int idxR = nums.length; // 定义target在左闭右开的区间里 [left, right)
        int idxM;
        while (idxL < idxR) {
            idxM = (idxL + idxR) >> 1; // 也可以使用右移的方式实现
            if (nums[idxM] < target) {
                idxL = idxM + 1; // target 在右区间，在[middle + 1, right)中
            } else if (nums[idxM] > target) {
                idxR = idxM; // target 在左区间，在[left, middle)中
            } else {
                return idxM;
            }
        }
        return -1; // 未找到目标值
    }

2、双指针法

双指针法（快慢指针法）：通过一个快指针和慢指针在一个 for 循环下完成两个 for 循环的工作。定义快慢指针：

快指针：寻找新数组的元素，新数组就是不含有目标元素的数组
慢指针：指向更新，新数组下标的位置

2.1、移除元素

给定一个数组 nums 和一个值 val，你需要原地移除所有数值等于 val 的元素，并返回移除后数组的新长度。不要使用额外的数组空间，必须仅使用 O(1) 额外空间并原地修改输入数组。元素的顺序可以改变，不需要考虑数组中超出新长度后面的元素。

    public static int removeElement(int[] nums, int val) {
        int idxSlow = 0;
        for (int idxFast = 0; idxFast < nums.length; idxFast++) {
            if (nums[idxFast] != val) { // 当快指针指向的值不等于要移除的目标值时
                nums[idxSlow++] = nums[idxFast]; // 将快指针指向的值填充到慢指针指向的位置
            }
        }
        return idxSlow; // 因为循环中使用的是idxSlow++，所以这里直接返回的就是新数组长度
    }

2.2、有序数组的平方

给定一个按非递减顺序排序的整数数组 nums，返回每个数字的平方组成的新数组，要求也按非递减顺序排序。

数组其实是有序的，只不过负数平方之后可能成为最大数了。那么数组平方的最大值就在数组的两端，不是最左边就是最右边，不可能是中间，此时可以考虑双指针法了，i 指向起始位置，j 指向终止位置。定义一个新数组 result，和 A 数组一样的大小，让 k 指向 result 数组终止位置。

如果 A[i] _ A[i] < A[j] _ A[j] 那么 result[k--] = A[j] * A[j];
如果 A[i] _ A[i] >= A[j] _ A[j] 那么 result[k--] = A[i] * A[i];

    public static int[] sortedSquares(int[] nums) {
        int[] result = new int[nums.length];
        int idxP = result.length - 1;
        int idxS = 0;
        int idxE = nums.length - 1;
        int numS, numE;
        while (idxS <= idxE) {
            numS = nums[idxS] * nums[idxS];
            numE = nums[idxE] * nums[idxE];
            if (numS > numE) {
                result[idxP--] = numS;
                idxS++;
            } else {
                result[idxP--] = numE;
                idxE--;
            }
        }
        return result;
    }

2.3、长度最小的子数组（滑动窗口）

给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的长度最小的连续子数组，并返回其长度。如果不存在符合条件的子数组，返回 0。

实现滑动窗口，主要确定如下三点：

窗口内是什么？满足其和 ≥ s 的长度最小的连续子数组。
如何移动窗口的起始位置？如果当前窗口的值大于等于 s 了，窗口就要向前移动了（也就是该缩小了）。
如何移动窗口的结束位置？窗口的结束位置就是遍历数组的指针，也就是 for 循环里的索引。

    public static int minSubArrayLen(int[] nums, int s) {
        int idxS = 0;
        int subSum = 0;
        int result = Integer.MAX_VALUE;
        for (int idxE = 0; idxE < nums.length; idxE++) {
            subSum += nums[idxE];
            while (subSum >= s) {
                result = Math.min(result, idxE - idxS + 1);
                subSum -= nums[idxS++];
            }
        }
        return result == Integer.MAX_VALUE ? 0 : result;
    }

3、前缀和

前缀和的思想是重复利用计算过的子数组之和，从而降低区间查询需要累加计算的次数。

3.1、区间和

给定一个整数数组 Array，请计算该数组在每个指定区间内元素的总和。

输入描述：第一行输入为整数数组 Array 的长度 n，接下来 n 行，每行一个整数，表示数组的元素。随后的输入为需要计算总和的区间，直至文件结束。

输出描述：输出每个指定区间内元素的总和。

输入示例：

输出示例：

3
9

数据范围：0 < n <= 100000

解题思路：在处理输入时，先将数组的前缀和存储起来，然后根据区间的起始和结束位置，直接计算出区间内的总和。

import java.util.Scanner;

public class RangeSum {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] arr = new int[n];
        int[] sum = new int[n];
        int presum = 0;
        for (int i = 0; i < n; i++) {
            arr[i] = scanner.nextInt();
            presum += arr[i];
            sum[i] = presum;
        }
        while (scanner.hasNextInt()) {
            int s = scanner.nextInt();
            int e = scanner.nextInt();
            int result;
            if (s == 0) {
                result = sum[e];
            } else {
                result = sum[e] - sum[s - 1];
            }
            System.out.println(result);
        }
        scanner.close();
    }
}

3.2、开发商购买土地

在一个城市区域内，被划分成了 n * m 个连续的区块，每个区块都拥有不同的权值，代表着其土地价值。目前，有两家开发公司，A 公司和 B 公司，希望购买这个城市区域的土地。现在，需要将这个城市区域的所有区块分配给 A 公司和 B 公司。然而，由于城市规划的限制，只允许将区域按横向或纵向划分成两个子区域，而且每个子区域都必须包含一个或多个区块。为了确保公平竞争，你需要找到一种分配方式，使得 A 公司和 B 公司各自的子区域内的土地总价值之差最小。注意：区块不可再分。

输入描述：第一行输入两个正整数，代表 n 和 m；接下来的 n 行，每行输出 m 个正整数。

输出描述：请输出一个整数，代表两个子区域内土地总价值之间的最小差距。

输入示例：

输出示例：

提示信息：

如果将区域按照如下方式划分，两个子区域内土地总价值之间的最小差距可以达到 0。
1 2 | 3
2 1 | 3
1 2 | 3

数据范围：1 <= n, m <= 100；n 和 m 不同时为 1。

解题思路：可以使用前缀和的思路来求解，先将行方向，和列方向的和求出来，这样可以方便知道划分的两个区间的和。

import java.util.Scanner;

public class SplitLands {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        int[] hSum = new int[n]; // 统计横向
        int[] vSum = new int[m]; // 统计纵向
        int num;
        int sum = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                num = scanner.nextInt();
                hSum[i] += num;
                vSum[j] += num;
                sum += num;
            }
        }

        int result = Integer.MAX_VALUE;
        int hCut = 0;
        for (int i = 0; i < n; i++) {
            hCut += hSum[i];
            result = Math.min(result, Math.abs((sum - hCut) - hCut));
            // 更新result。其中，hCut表示前i行的和，sum - hCut表示剩下的和，作差、取绝对值，得到题目需要的“A和B各自的子区域内的土地总价值之差”。下同。
        }
        int vCut = 0;
        for (int j = 0; j < m; j++) {
            vCut += vSum[j];
            result = Math.min(result, Math.abs((sum - vCut) - vCut));
        }
        System.out.println(result);
        scanner.close();
    }
}

01.Array（数组）

0、 基础理论

1、 二分查找

1.1、 方法一（左闭右闭）

1.2、 方法二（左闭右开）

2、 双指针法

2.1、 移除元素

2.2、 有序数组的平方

2.3、 长度最小的子数组（滑动窗口）

3、 前缀和

3.1、 区间和

3.2、 开发商购买土地