标签： 二分查找

目标

给你一个整数数组 nums 和一个整数 x 。每一次操作时，你应当移除数组 nums 最左边或最右边的元素，然后从 x 中减去该元素的值。请注意，需要 修改 数组以供接下来的操作使用。

如果可以将 x 恰好 减到 0 ，返回 最小操作数 ；否则，返回 -1 。

示例 1：

输入：nums = [1,1,4,2,3], x = 5
输出：2
解释：最佳解决方案是移除后两个元素，将 x 减到 0 。

示例 2：

输入：nums = [5,6,7,8,9], x = 4
输出：-1

示例 3：

输入：nums = [3,2,20,1,1,3], x = 10
输出：5
解释：最佳解决方案是移除后三个元素和前两个元素（总共 5 次操作），将 x 减到 0 。

说明：

• 1 <= nums.length <= 10^5
• 1 <= nums[i] <= 10^4
• 1 <= x <= 10^9

思路

有一个正整数数组 nums，每一次操作可以移除剩余数组的最左或最右元素，求移除元素和等于 x 的最小操作数，如果不存在则返回 -1。

将问题转化为求子数组和为 sum - x 的最大长度，可以使用滑动窗口。

代码

/**
 * @date 2026-09-23 8:49
 */
public class MinOperations1658 {

    public int minOperations(int[] nums, int x) {
        int n = nums.length;
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        if (sum < x) {
            return -1;
        } else if (sum == x) {
            return n;
        }
        int target = sum - x;
        int res = 0;
        int l = 0;
        sum = 0;
        for (int r = 0; r < n; r++) {
            sum += nums[r];
            while (sum > target) {
                sum -= nums[l++];
            }
            if (sum == target) {
                res = Math.max(res, r - l + 1);
            }
        }
        return res == 0 ? -1 : n - res;
    }

}

性能

目标

给你一个整数数组 arr 和一个整数值 target 。

请你在 arr 中找 两个互不重叠的子数组 且它们的和都等于 target 。可能会有多种方案，请你返回满足要求的两个子数组长度和的 最小值 。

请返回满足要求的最小长度和，如果无法找到这样的两个子数组，请返回 -1 。

示例 1：

输入：arr = [3,2,2,4,3], target = 3
输出：2
解释：只有两个子数组和为 3 （[3] 和 [3]）。它们的长度和为 2 。

示例 2：

输入：arr = [7,3,4,7], target = 7
输出：2
解释：尽管我们有 3 个互不重叠的子数组和为 7 （[7], [3,4] 和 [7]），但我们会选择第一个和第三个子数组，因为它们的长度和 2 是最小值。

示例 3：

输入：arr = [4,3,2,6,2,3,4], target = 6
输出：-1
解释：我们只有一个和为 6 的子数组。

示例 4：

输入：arr = [5,5,4,4,5], target = 3
输出：-1
解释：我们无法找到和为 3 的子数组。

示例 5：

输入：arr = [3,1,1,1,5,1,2,1], target = 3
输出：3
解释：注意子数组 [1,2] 和 [2,1] 不能成为一个方案因为它们重叠了。

说明：

• 1 <= arr.length <= 10^5
• 1 <= arr[i] <= 1000
• 1 <= target <= 10^8

思路

有一个整数数组 arr 和一个整数值 target，从数组中找到两个不重叠的子数组，使得子数组的和为 target，返回这两个子数组长度之和的最小值。

将重叠问题进行前后缀分解，在各自的部分只需考虑和为 target 的最小长度，最小长度可以使用滑动窗口。

代码

/**
 * @date 2026-09-17 10:06
 */
public class MinSumOfLengths1477 {

    public int minSumOfLengths(int[] arr, int target) {
        int n = arr.length;
        int[] pre = new int[n + 1];
        int[] suf = new int[n + 1];
        Arrays.fill(pre, Integer.MAX_VALUE);
        Arrays.fill(suf, Integer.MAX_VALUE);
        int sum = 0;
        int l = 0;
        for (int i = 0; i < n; i++) {
            sum += arr[i];
            while (sum > target) {
                sum -= arr[l++];
            }
            if (sum == target) {
                pre[i + 1] = Math.min(pre[i], i - l + 1);
            } else {
                pre[i + 1] = pre[i];
            }
        }
        sum = 0;
        int r = n - 1;
        for (int i = n - 1; i >= 0; i--) {
            sum += arr[i];
            while (sum > target) {
                sum -= arr[r--];
            }
            if (sum == target) {
                suf[i] = Math.min(suf[i + 1], r - i + 1);
            } else {
                suf[i] = suf[i + 1];
            }
        }
        int res = Integer.MAX_VALUE;
        for (int i = 0; i < n; i++) {
            if (pre[i + 1] != Integer.MAX_VALUE && suf[i + 1] != Integer.MAX_VALUE) {
                res = Math.min(res, pre[i + 1] + suf[i + 1]);
            }
        }
        return res == Integer.MAX_VALUE ? -1 : res;
    }

}

性能

目标

给你一个整数 n，表示图中的节点数量，这些节点按从 0 到 n - 1 编号。

同时给你一个长度为 n 的整数数组 nums，该数组按 非递减 顺序排序，以及一个整数 maxDiff。

如果满足 |nums[i] - nums[j]| <= maxDiff（即 nums[i] 和 nums[j] 的 绝对差 至多为 maxDiff），则节点 i 和节点 j 之间存在一条 无向边 。

此外，给你一个二维整数数组 queries。对于每个 queries[i] = [ui, vi]，需要判断节点 ui 和 vi 之间是否存在路径。

返回一个布尔数组 answer，其中 answer[i] 等于 true 表示在第 i 个查询中节点 ui 和 vi 之间存在路径，否则为 false。

示例 1：

输入: n = 2, nums = [1,3], maxDiff = 1, queries = [[0,0],[0,1]]
输出: [true,false]
解释:
查询 [0,0]：节点 0 有一条到自己的显然路径。
查询 [0,1]：节点 0 和节点 1 之间没有边，因为 |nums[0] - nums[1]| = |1 - 3| = 2，大于 maxDiff。
因此，在处理完所有查询后，最终答案为 [true, false]。

示例 2：

输入: n = 4, nums = [2,5,6,8], maxDiff = 2, queries = [[0,1],[0,2],[1,3],[2,3]]
输出: [false,false,true,true]
解释:
生成的图如下：
查询 [0,1]：节点 0 和节点 1 之间没有边，因为 |nums[0] - nums[1]| = |2 - 5| = 3，大于 maxDiff。
查询 [0,2]：节点 0 和节点 2 之间没有边，因为 |nums[0] - nums[2]| = |2 - 6| = 4，大于 maxDiff。
查询 [1,3]：节点 1 和节点 3 之间存在路径通过节点 2，因为 |nums[1] - nums[2]| = |5 - 6| = 1 和 |nums[2] - nums[3]| = |6 - 8| = 2，都小于等于 maxDiff。
查询 [2,3]：节点 2 和节点 3 之间有一条边，因为 |nums[2] - nums[3]| = |6 - 8| = 2，等于 maxDiff。
因此，在处理完所有查询后，最终答案为 [false, false, true, true]。

说明：

• 1 <= n == nums.length <= 10^5
• 0 <= nums[i] <= 10^5
• nums 按 非递减 顺序排序。
• 0 <= maxDiff <= 10^5
• 1 <= queries.length <= 10^5
• queries[i] == [ui, vi]
• 0 <= ui, vi < n

思路

有 n 个节点编号为 0 ~ n - 1，节点之间的边由非递减数组 nums 与变量 maxDiff 给出，如果两个节点的差值不超过 maxDiff 则表示它们之间有一条无向边。有一个查询数组 queries，返回每次查询的两个节点是否连通。

由于 nums 非递减，只需考虑相邻节点是否连通即可。如果相邻节点不连通，那么跨过这对节点的区间都不连通。可以使用并查集维护连通性。

代码

/**
 * @date 2026-07-09 8:50
 */
public class PathExistenceQueries3532 {

    class UnionFind {
        private final int[] fa;

        public UnionFind(int n) {
            fa = new int[n];
            Arrays.setAll(fa, i -> i);
        }

        public int find(int i) {
            if (i != fa[i]) {
                fa[i] = find(fa[i]);
            }
            return fa[i];
        }

        public void union(int a, int b) {
            int x = find(a);
            int y = find(b);
            if (x < y) {
                fa[y] = x;
            } else if (x > y) {
                fa[x] = y;
            }
        }
    }

    public boolean[] pathExistenceQueries(int n, int[] nums, int maxDiff, int[][] queries) {
        UnionFind uf = new UnionFind(n);
        for (int i = 1; i < n; i++) {
            if (Math.abs(nums[i] - nums[i - 1]) <= maxDiff) {
                uf.union(i, i - 1);
            }
        }
        boolean[] res = new boolean[queries.length];
        for (int i = 0; i < queries.length; i++) {
            res[i] = uf.find(queries[i][0]) == uf.find(queries[i][1]);
        }
        return res;
    }
}

性能

目标

整数数组 nums 按升序排列，数组中的值 互不相同 。

在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转，使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。

给你 旋转后 的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回 -1 。

你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。

示例 1：

输入：nums = [4,5,6,7,0,1,2], target = 0
输出：4

示例 2：

输入：nums = [4,5,6,7,0,1,2], target = 3
输出：-1

示例 3：

输入：nums = [1], target = 0
输出：-1

说明：

• 1 <= nums.length <= 5000
• -10^4 <= nums[i] <= 10^4
• nums 中的每个值都 独一无二
• 题目数据保证 nums 在预先未知的某个下标上进行了旋转
• -10^4 <= target <= 10^4

思路

数组 nums的 元素值互不相同，它由一个升序数组经过旋转而成，返回 target 在数组中的下标，如果不在返回 -1，要求时间复杂度为 O(log n)。

所谓的旋转可以理解为以 k 为分界点将数组分为两段，后面的放到前面，前面的放到后面。相当于两个有序数组拼在一起，且前面数组的每个元素都比后面数组的每个元素都大。

• 如果 target 在左侧，m 在右侧，直接排除右侧
• 如果 target 在右侧，m 在左侧，直接排除左侧
• 如果在同一侧直接按照正常的有序二分即可

进阶的版本是 81.搜索旋转排序数组II。

代码

/**
 * @date 2026-05-22 09:13
 */
public class Search33 {

    public int search_v3(int[] nums, int target) {
        int r = nums.length - 1, l = 0;
        int m = l + (r - l) / 2;
        while (l <= r) {
            // 如果 target 在左侧，m 在右侧，直接排除右侧
            if (target >= nums[0] && nums[m] < nums[0]) {
                r = m - 1;
            } else if (target < nums[0] && nums[m] >= nums[0]) {
                // 如果 target 在右侧，m 在左侧，直接排除左侧
                l = m + 1;
                // 如果在同一侧直接按照正常的有序二分即可
            } else if (nums[m] == target) {
                return m;
            } else if (nums[m] < target) {
                l = m + 1;
            } else {
                r = m - 1;
            }
            m = l + (r - l) / 2;
        }
        return -1;
    }

}

性能