顺序列举、组合列举、排列列举

15.2 顺序列举的算法设计

这类问题通常是处理一个序列（比如数组、字符串），我们要找的是其中满足特定条件的、连续的一部分。

15.2.1 最大连续 1 的个数

题目：给定一个二进制数组 nums ，计算其中最大连续 1 的个数。

拿到这个题，第一反应是什么？找“连续的1”，那我就把所有可能的“连续段”都找出来，看看哪个段里的1最多。

解法一：暴力枚举所有子数组 O(N²)

最无脑的办法，就是两层循环。第一层循环i定开头，第二层循环j定结尾，然后去数[i...j]这个区间里是不是全是1。

public int findMaxConsecutiveOnes_1(int[] nums) {
    int maxCount = 0;
    for (int i = 0; i < nums.length; i++) {
        for (int j = i; j < nums.length; j++) {
            // 现在我们有了一个子数组 [i, j]
            //
            // 接下来，检查这个子数组是否全是1
            boolean allOnes = true;
            for (int k = i; k <= j; k++) {
                if (nums[k] == 0) {
                    allOnes = false;
                    break;
                }
            }
            if (allOnes) {
                maxCount = Math.max(maxCount, j - i + 1);
            }
        }
    }
    return maxCount;
}

这代码太暴力了，三层循环，实际上是O(N³)。我们可以优化一下，第二层循环里直接计算，省掉第三层。

public int findMaxConsecutiveOnes_1_Optimized(int[] nums) {
    int maxCount = 0;
    for (int i = 0; i < nums.length; i++) {
        if (nums[i] == 1) {
            // 从i开始向后数
            int currentCount = 0;
            for (int j = i; j < nums.length; j++) {
                if (nums[j] == 1) {
                    currentCount++;
                } else {
                    // 遇到0就断了
                    break;
                }
            }
            maxCount = Math.max(maxCount, currentCount);
        }
    }
    return maxCount;
}

这个版本好一点，O(N²)，但还是慢。为啥慢？因为我们重复计算了很多东西。比如[1,1,1]，我们算了[1]，[1,1]，[1,1,1]，然后又从第二个1开始算[1]，[1,1]…… 完全没必要。

解法二：一次遍历，打断计数 O(N)

这个思路就顺畅多了。我从头到尾走一遍不就行了么？

准备两个变量，一个maxCount记录全局最大值，一个currentCount记录当前连续1的个数。遍历数组：

如果遇到 1，currentCount 就加一。
如果遇到 0，说明连续的1断了。这时候，我得拿当前的currentCount和maxCount比一下，更新maxCount。然后， currentCount清零，准备下一次计数。

public int findMaxConsecutiveOnes_2(int[] nums) {
    int maxCount = 0;
    int currentCount = 0;
    for (int num : nums) {
        if (num == 1) {
            currentCount++;
        } else {
            // 连续中断，结算一次
            maxCount = Math.max(maxCount, currentCount);
            // 当前计数清零
            currentCount = 0;
        }
    }
    // 最后还要结算一次，防止数组以1结尾，比如 [1,1,1]
    maxCount = Math.max(maxCount, currentCount);
    return maxCount;
}

这个解法只遍历了一遍数组，时间复杂度是O(N)，空间是O(1)，非常理想。

解法三：思路转换（其实是解法二的变体）

我能不能把问题看成是被 0 分割的多个由 1 组成的段落？我只需要找出最长的那个段落就行。这其实和解法二的思路内核是一样的，只是表述方式不同，代码实现上可以稍微变化。

public int findMaxConsecutiveOnes_3(int[] nums) {
    int maxCount = 0;
    int currentCount = 0;
    for (int num : nums) {
        // 核心：遇到1就累加，遇到0就归零
        currentCount = (num == 0) ? 0 : currentCount + 1;
        maxCount = Math.max(maxCount, currentCount);
    }
    return maxCount;
}

这个写法更简洁，用一个三元运算符就把逻辑搞定了。它把“结算”的动作融入到了每一次循环中，而不是只在遇到0的时候才结算。

小结：从 O(N²) 到 O(N)，我们去掉的是冗余的、重复的计算。关键在于意识到，当连续性被打破时，之前的信息就可以被“结算”并抛弃，我们只需要轻装上阵，继续前进。

15.2.2 数组中两元素的最大乘积

题目：给你一个整数数组 nums，请你选择数组的两个不同下标 i 和 j，使 (nums[i]-1)*(nums[j]-1) 的值最大。

直觉很简单：要想乘积最大，两个乘数就得最大。所以问题就转化成了，找到数组里最大的两个数。

解法一：暴力枚举 O(N²)

不整那些虚的，直接两层循环，把所有可能的 (i, j) 对都试一遍，找出最大乘积。

public int maxProduct_1(int[] nums) {
    int maxProd = 0;
    int n = nums.length;
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            // 确保 i 和 j 是不同下标
            int currentProd = (nums[i] - 1) * (nums[j] - 1);
            if (currentProd > maxProd) {
                maxProd = currentProd;
            }
        }
    }
    return maxProd;
}

标准的暴力美学，简单直接，虽然效率不高，但保底能做出来。

解法二：排序 O(N log N)

暴力解的瓶颈在于“找”最大的两个数太慢。那有什么快速的方法找最大数？排序啊！

把数组一排，最大的两个数自然就跑到队尾去了。

import java.util.Arrays;

public int maxProduct_2(int[] nums) {
    Arrays.sort(nums);
    int n = nums.length;
    // 最大的两个数在数组末尾
    return (nums[n - 1] - 1) * (nums[n - 2] - 1);
}

代码干净利落。时间复杂度主要来自排序的 O(N log N)。比暴力解好多了。

解法三：一次遍历 O(N)

再想想，我真的需要给整个数组排序吗？我其实只关心那两个最大的数，其他数的顺序我根本不care。这就好比选班里身高最高的两个人，我需要把全班按身高排个队吗？不需要，我扫一眼，心里记着当前最高的和第二高的就行了。

public int maxProduct_3(int[] nums) {
    // 初始化为两个最小的值，或者数组的前两个元素
    int max1 = 0; // 最大值
    int max2 = 0; // 次大值

    for (int num : nums) {
        if (num >= max1) {
            // 当前数比最大值还大
            max2 = max1; // 原来的最大值变成次大值
            max1 = num;  // 更新最大值
        } else if (num > max2) {
            // 当前数在最大和次大之间
            max2 = num;
        }
    }
    return (max1 - 1) * (max2 - 1);
}

只遍历一次，不需要额外空间，时间复杂度O(N)。这就是这个问题的最优解了。我们通过维护两个变量，就避免了全局排序这个“杀鸡用牛刀”的操作。

小结：解决问题的关键是抓住主要矛盾。这个问题的主要矛盾是“找到最大的两个数”，而不是“给所有数排序”。明确了这一点，O(N)的解法就水到渠成了。

15.2.3 连续整数求和

题目：给定一个正整数 n，返回 n 可以表示的连续正整数序列和的方案数。

比如 n=15，可以有 15, 7+8, 4+5+6, 1+2+3+4+5，所以返回4。

解法一：暴力枚举起点和终点 O(N²)

还是老套路，我不知道从哪开始，也不知道多长，那我就都试试。

外层循环 i 作为连续序列的起点。
内层循环 j 从 i 开始累加，直到和等于或大于 n。

public int consecutiveNumbersSum_1(int n) {
    int count = 0;
    for (int i = 1; i <= n; i++) { // i 是起点
        int sum = 0;
        for (int j = i; j <= n; j++) { // j 是终点
            sum += j;
            if (sum == n) {
                count++;
                break; // 找到了，这个起点没必要再往后加了
            }
            if (sum > n) {
                break; // 超过了，这个起点也没戏了
            }
        }
    }
    return count;
}

这个解法非常直观，但对于大的 n，比如 10^9，O(N^2) 肯定超时。

解法二：数学公式 + 枚举长度 O(√N)

暴力解太慢，得换个角度。我们假设这个连续序列的长度是 k，首项是 x。那么这个序列就是 x, x+1, ..., x+k-1。根据等差数列求和公式：Sum = (首项 + 末项) * 项数 / 2 n = (x + x+k-1) * k / 2 n = (2x + k - 1) * k / 2 2n = k(2x + k - 1)

这个公式是我们的核心。我们要求的是有多少个这样的 (x, k) 对，其中 x >= 1，k >= 1。

我们可以把 k 作为枚举的目标。 2x = 2n/k - k + 1 因为 x >= 1，所以 2x >= 2， 2n/k - k + 1 >= 2 2n/k >= k + 1 2n >= k(k+1) 这给我们 k 的范围提供了一个约束。我们可以从 k=1 开始枚举，直到 k(k+1) > 2n 为止。对于每个 k，我们检查 2n 是否能被 k 整除，并且 2n/k - k + 1 是否是一个正偶数（因为它是 2x）。

2n/k - k + 1 > 0 并且 (2n/k - k + 1) % 2 == 0 2n/k > k - 1 又因为我们已经约束了 2n >= k(k+1)，所以 2n/k >= k+1 > k-1，第一个条件自然满足。我们只需要检查 (2n/k - k + 1) 是不是偶数。也就是 2n/k - k 是不是奇数。

如果 k 是奇数，2n/k 是偶数，2n/k - k 必然是奇数。
如果 k 是偶数，2n/k 可能是奇数或偶数，2n/k - k 的奇偶性取决于 2n/k。

综合一下判断条件：对于一个 k，如果 2n 能被 k 整除，并且 (2n/k -k + 1) 是正偶数，就算一个解。

public int consecutiveNumbersSum_2(int n) {
    int count = 0;
    // k*(k+1) <= 2n  大致是 k <= sqrt(2n)
    for (int k = 1; k * (k - 1) / 2 < n; k++) {
        // 检查 (n - k*(k-1)/2) 是否能被 k 整除
        if ((n - k * (k - 1) / 2) % k == 0) {
            count++;
        }
    }
    return count;
}

这个解法的时间复杂度降到了 O(√N)，对于 10^9 的 n 也可以接受。

解法三：纯数学-因子分解 O(logN) 或 O(N^(1/3))

我们再回到公式 2n = k(2x + k - 1)。令 A = k，B = 2x + k - 1。 B - A = (2x + k - 1) - k = 2x - 1，这是一个奇数。这说明 A 和 B 的奇偶性必然不同，一个奇数一个偶数。

问题转化成了：把 2n 分解成两个因子 A 和 B (A*B=2n)，要求 B > A (因为2x-1 > 0) 并且 A和B一奇一偶。因为A*B是2n(偶数)，A和B不可能都是奇数。所以只要A和B不都是偶数就行。换句话说，A和B不能同时是偶数。

怎么保证它们不同时是偶数？只要把 2n 所有 2 的因子都分给其中一个数就行。设 2n = 2^p * m，其中 m 是奇数。把 2^p 整体作为一个包，去和 m 的因子组合。 m 的任何一个奇数因子 d，都可以和 2^p 组合，形成 A = d，B=2^p*(m/d) 或者 A = 2^p * d，B = m/d。只要满足 B > A，就是一个合法的解。

事实上，对于 n 的每一个奇数因子 d，都可以唯一对应一个连续和序列。比如 n = 15 = 3 * 5。奇数因子有 1, 3, 5, 15。

d=1: n/1=15, 长度1，序列 15
d=3: n/3=5, 长度3, 中位数5, 序列 4,5,6
d=5: n/5=3, 长度5, 中位数3, 序列 1,2,3,4,5
d=15: n/15=1, 长度15, 中位数1... impossible for positive integers.

这个规律是：n 的奇数因子个数，就是 n 可以被表示为连续正整数和的方案数。所以问题最终变成了：求 n 的奇数因子有多少个。

如何求？先把n中所有的因子2都除掉，剩下的数 m 的因子个数就是答案。 n = 2^p * m 我们只需要求 m 的因子数。

public int consecutiveNumbersSum_3(int n) {
    // 1. 把n中的因子2全部除掉
    while (n % 2 == 0) {
        n /= 2;
    }
    // 2. n现在是一个奇数了，求n的因子个数
    int count = 1;
    for (int i = 3; i * i <= n; i += 2) {
        if (n % i == 0) {
            int exponent = 0;
            while (n % i == 0) {
                exponent++;
                n /= i;
            }
            count *= (exponent + 1);
        }
    }
    // 如果n本身在分解后还是一个大于1的质数
    if (n > 1) {
        count *= 2;
    }
    return count;
}

这个解法通过纯粹的数学变换，把问题降维成了一个数论问题，效率极高。

小结：从 O(N²) 的模拟，到 O(√N) 的公式枚举，再到因子分解的 O(logN) 级别解法，这个题完美地展示了数学在算法优化中的威力。

15.2.4 电话号码的字母组合

题目：给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。

这是典型的“多种可能性的组合”问题，是穷举思想的直接体现。

解法一：回溯 (DFS)

回溯法是解决这类组合、排列、子集问题的万能钥匙。它的思想就像是走迷宫，一条路走到黑，走不通了就退回来，换条路再走。

定义一个递归函数 backtrack(combination, next_digits)。
combination 是当前已经拼好的字符串。
next_digits 是剩下还没处理的数字。
递归出口：如果 next_digits 为空，说明一个完整的组合已经产生，把它加入结果列表。
递归过程：
1. 取出 next_digits 的第一个数字。
2. 找到这个数字对应的所有字母（比如'2'对应'a','b','c'）。
3. 遍历这些字母：
  - 把当前字母拼接到 combination 后面。
  - 带着新的 combination 和去掉第一个数字的 next_digits，继续递归调用 backtrack。
  - （这一步很关键，虽然在Java中String是不可变的，传递的是新对象，但如果是用StringBuilder，就需要“回溯”操作，即删除刚添加的字母）

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

class LetterCombinations {
    private final Map<Character, String> phoneMap = Map.of(
            '2', "abc", '3', "def", '4', "ghi", '5', "jkl",
            '6', "mno", '7', "pqrs", '8', "tuv", '9', "wxyz"
    );
    private List<String> result = new ArrayList<>();

    public List<String> letterCombinations_1(String digits) {
        if (digits == null || digits.isEmpty()) {
            return result;
        }
        backtrack(new StringBuilder(), digits, 0);
        return result;
    }

    private void backtrack(StringBuilder combination, String digits, int index) {
        if (index == digits.length()) {
            result.add(combination.toString());
            return;
        }

        char digit = digits.charAt(index);
        String letters = phoneMap.get(digit);
        for (char letter : letters.toCharArray()) {
            combination.append(letter);
            backtrack(combination, digits, index + 1);
            // 回溯，撤销选择
            combination.deleteCharAt(combination.length() - 1);
        }
    }
}

回溯法思路清晰，是这类问题的标准解。

解法二：队列 (BFS)

我们也可以用广度优先搜索的思路来解决。把问题想象成一棵树，每一层代表一个数字，我们要做的就是层序遍历。

创建一个队列，初始时，如果输入不为空，就把第一个数字对应的每个字母作为单独的字符串放进去。比如输入是"23"，队列初始为 ["a", "b", "c"]。
然后处理第二个数字'3'（对应'd','e','f'）。
不断地从队列头部取出元素，和'3'对应的每个字母拼接，再放回队列尾部。
- 取出 "a"，拼接成 "ad", "ae", "af"，放入队列。
- 取出 "b"，拼接成 "bd", "be", "bf"，放入队列。
- 取出 "c"，拼接成 "cd", "ce", "cf"，放入队列。
当处理完所有数字后，队列里剩下的就是所有结果。

import java.util.LinkedList;
import java.util.List;
import java.util.Map;

public List<String> letterCombinations_2(String digits) {
    LinkedList<String> queue = new LinkedList<>();
    if (digits == null || digits.isEmpty()) {
        return queue;
    }

    // 不要用之前的Map.of，因为这里可能需要处理1等特殊数字，虽然题目说2-9
    String[] mapping = new String[] {"0", "1", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};

    queue.add(""); // 初始状态

    for (int i = 0; i < digits.length(); i++) {
        int digit = Character.getNumericValue(digits.charAt(i));
        // 只处理当前层级的节点
        while (queue.peek().length() == i) {
            String current = queue.remove();
            for (char c : mapping[digit].toCharArray()) {
                queue.add(current + c);
            }
        }
    }
    return queue;
}

BFS的解法是迭代的，避免了递归的栈开销，对于某些场景可能更优。

解法三：纯迭代构建

这个方法和BFS有点像，但更直接。

结果列表result初始化为 [""]。
遍历输入的每一个数字：
- 创建一个临时的列表 tempResult。
- 遍历result中的每一个已有字符串s。
- 遍历当前数字对应的每一个字母c。
- 把s + c加入到tempResult中。
- 遍历完后，用tempResult替换result。
循环结束，result就是最终答案。

public List<String> letterCombinations_3(String digits) {
    List<String> result = new ArrayList<>();
    if (digits == null || digits.isEmpty()) {
        return result;
    }

    String[] mapping = new String[] {"0", "1", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
    result.add("");

    for (char digitChar : digits.toCharArray()) {
        List<String> tempResult = new ArrayList<>();
        int digit = Character.getNumericValue(digitChar);
        String letters = mapping[digit];

        for (String s : result) {
            for (char c : letters.toCharArray()) {
                tempResult.add(s + c);
            }
        }
        result = tempResult; // 更新结果集
    }
    return result;
}

这个方法一步步地构建结果集，每处理一个数字，结果集就“膨胀”一次，直到处理完所有数字。

小结：回溯法(DFS)和队列法(BFS)是解决此类组合问题的两大经典思路，一个深度优先，一个广度优先。纯迭代构建是BFS思想的一种更直接的实现。三种方法各有千秋，但核心都是穷举所有可能性。

（篇幅原因，后续题目将采用相同的分析结构继续）

15.2.5 数组中的最长山脉

题目：寻找数组中最长的一座“山脉”的长度。“山脉”定义为需要先严格递增，再严格递减。

解法一：枚举山顶 O(N²) 最直观的，山脉总得有个山顶吧？那我就枚举数组里每个点，看它能不能当山顶。一个点i是山顶，必须满足 arr[i] > arr[i-1] 且 arr[i] > arr[i+1]。找到一个可能的山顶后，就向左向右分别延伸，统计长度。

public int longestMountain_1(int[] arr) {
    if (arr == null || arr.length < 3) return 0;
    int maxLength = 0;
    for (int i = 1; i < arr.length - 1; i++) {
        // 判断i是否为山顶
        if (arr[i] > arr[i - 1] && arr[i] > arr[i + 1]) {
            int left = i - 1;
            while (left > 0 && arr[left - 1] < arr[left]) {
                left--;
            }
            int right = i + 1;
            while (right < arr.length - 1 && arr[right] > arr[right + 1]) {
                right++;
            }
            maxLength = Math.max(maxLength, right - left + 1);
        }
    }
    return maxLength;
}

代码好理解，但效率不高，因为向左向右延伸时，很多元素被重复扫描了。

解法二：状态机一次遍历 O(N) 我们可以用一个状态机来模拟爬山的过程：start(山脚), up(上坡), down(下坡)。

遍历数组，维护一个upLen和downLen。
如果当前元素比前一个大（上坡）：
- 如果之前在下坡，说明一座山走完了，结算长度，然后重置upLen=1, downLen=0。
- 否则，upLen++。
如果当前元素比前一个小（下坡）：
- 如果之前在上坡或下坡，说明是合法的下坡，downLen++。
如果当前元素和前一个相等（平地）：
- 结算之前的山，然后全部重置。
每次在下坡时（downLen > 0），并且之前有过上坡（upLen>0），就计算当前山脉长度 upLen + downLen + 1 并更新最大值。

public int longestMountain_2(int[] arr) {
    if (arr == null || arr.length < 3) return 0;
    int n = arr.length;
    int maxLength = 0;
    int i = 0;
    while (i < n - 1) {
        // 找到上坡的起点
        while (i < n - 1 && arr[i] >= arr[i + 1]) {
            i++;
        }
        int upStart = i;
        // 走上坡
        while (i < n - 1 && arr[i] < arr[i + 1]) {
            i++;
        }
        int peak = i;
        // 走下坡
        while (i < n - 1 && arr[i] > arr[i + 1]) {
            i++;
        }
        int downEnd = i;
        // 如果确实有上坡和下坡
        if (peak > upStart && downEnd > peak) {
            maxLength = Math.max(maxLength, downEnd - upStart + 1);
        }
        // 防止平地 [1,2,2,1] 这种情况，i卡住
        if (i == peak) {
             i++;
        }
    }
    return maxLength;
}

这个解法只遍历一次，是O(N)的。

解法三：动态规划 O(N) 用空间换时间。创建两个DP数组:

left[i]：表示以i结尾的、最长的连续递增子序列的长度。
right[i]：表示以i开头的、最长的连续递减子序列的长度。 left数组从左到右遍历计算，right数组从右到左遍历计算。最后再遍历一遍，对于每个i，如果left[i] > 1且right[i] > 1，说明i可以作为山顶，山脉长度为 left[i] + right[i] - 1。

public int longestMountain_3(int[] arr) {
    if (arr == null || arr.length < 3) return 0;
    int n = arr.length;
    int[] left = new int[n];
    int[] right = new int[n];

    // 从左到右计算递增序列
    for (int i = 1; i < n; i++) {
        if (arr[i] > arr[i - 1]) {
            left[i] = left[i - 1] + 1;
        }
    }

    // 从右到左计算递减序列
    for (int i = n - 2; i >= 0; i--) {
        if (arr[i] > arr[i + 1]) {
            right[i] = right[i + 1] + 1;
        }
    }

    int maxLength = 0;
    for (int i = 0; i < n; i++) {
        // 山顶必须有左坡和右坡
        if (left[i] > 0 && right[i] > 0) {
            maxLength = Math.max(maxLength, left[i] + right[i] + 1);
        }
    }
    return maxLength;
}

时间复杂度O(N)，空间复杂度O(N)。思路清晰，但需要额外空间。

15.2.6 长度最小的子数组

题目：给定一个含有 n 个正整数的数组和一个正整数 target 。找出该数组中满足其和 ≥ target 的长度最小的 连续子数组。

解法一：暴力枚举 O(N²) 简单粗暴，双层循环枚举所有连续子数组，计算和，更新最小长度。

public int minSubArrayLen_1(int target, int[] nums) {
    int minLen = Integer.MAX_VALUE;
    for (int i = 0; i < nums.length; i++) {
        int sum = 0;
        for (int j = i; j < nums.length; j++) {
            sum += nums[j];
            if (sum >= target) {
                minLen = Math.min(minLen, j - i + 1);
                break; // 已经满足，从i开始的更长子数组没必要看了
            }
        }
    }
    return minLen == Integer.MAX_VALUE ? 0 : minLen;
}

O(N²)的解法，数据量一大就超时。

解法二：滑动窗口 O(N) 这是解决这类问题的经典方法。想象一个窗口在数组上滑动。

用两个指针 left 和 right 表示窗口的左右边界。
right 指针向右移动，扩大窗口，把新元素加到 sum 里。
当 sum >= target 时，我们找到了一个满足条件的窗口。记录下它的长度 right - left + 1，并与 minLen 比较。
然后，尝试缩小窗口：left 指针向右移动，把 nums[left] 从 sum 中减去。
持续缩小，直到 sum < target。这时，我们知道从left开始的最小窗口已经找到了。
继续移动right，重复上述过程。

public int minSubArrayLen_2(int target, int[] nums) {
    int minLen = Integer.MAX_VALUE;
    int left = 0;
    int sum = 0;
    for (int right = 0; right < nums.length; right++) {
        sum += nums[right];
        while (sum >= target) {
            minLen = Math.min(minLen, right - left + 1);
            sum -= nums[left];
            left++;
        }
    }
    return minLen == Integer.MAX_VALUE ? 0 : minLen;
}

每个元素最多被 left 和 right 指针各访问一次，所以时间复杂度是O(N)。

解法三：前缀和 + 二分查找 O(N log N) 这个思路比较巧妙。

先计算一个前缀和数组 prefixSum，prefixSum[i] 表示 nums[0...i-1] 的和。
nums[i...j] 的和就等于 prefixSum[j+1] - prefixSum[i]。
我们遍历 i 作为子数组的起点。对于每个 i，我们需要找到一个最小的 j，使得 prefixSum[j+1] - prefixSum[i] >= target。
变形一下：prefixSum[j+1] >= target + prefixSum[i]。
由于数组元素都是正数，prefixSum 数组是严格单调递增的。所以，我们可以在 prefixSum 数组中（从i+1到n的范围内）二分查找第一个大于等于 target + prefixSum[i] 的位置。

import java.util.Arrays;
public int minSubArrayLen_3(int target, int[] nums) {
    int n = nums.length;
    int minLen = Integer.MAX_VALUE;
    int[] prefixSum = new int[n + 1];
    for (int i = 0; i < n; i++) {
        prefixSum[i + 1] = prefixSum[i] + nums[i];
    }

    for (int i = 0; i <= n; i++) {
        // 目标值
        int searchTarget = target + prefixSum[i];
        // 在 prefixSum[i+1...] 中找第一个 >= searchTarget 的位置
        // Arrays.binarySearch 找得到返回索引，找不到返回 (-插入点 - 1)
        int bound = Arrays.binarySearch(prefixSum, i + 1, n + 1, searchTarget);
        if (bound < 0) {
            bound = -bound - 1;
        }
        if (bound <= n) {
            minLen = Math.min(minLen, bound - i);
        }
    }
    return minLen == Integer.MAX_VALUE ? 0 : minLen;
}

O(N log N)的复杂度，虽然不如滑动窗口，但提供了一个不同的解题视角。

15.2.7 加油站

题目：在一条环路上有 N 个加油站，每个加油站有 gas[i] 升油，从第 i 站到第 i+1 站需要 cost[i] 升油。找一个加油站作为起点，使得你能开着车绕环路一周。

解法一：暴力模拟 O(N²) 最直接的想法，就是把每个加油站都当成起点试一次。

外层循环 i 从 0到N-1，枚举起点。
内层循环模拟开车过程，从i出发，看能不能走完一圈。用一个变量 tank 记录油箱里的油。
如果中途tank < 0，说明从i出发不行，跳出内层循环，试下一个起点。
如果能走完一圈，返回i。
如果所有起点都试完了还不行，返回-1。

public int canCompleteCircuit_1(int[] gas, int[] cost) {
    int n = gas.length;
    for (int i = 0; i < n; i++) {
        int tank = 0;
        boolean possible = true;
        for (int j = 0; j < n; j++) {
            int currentStation = (i + j) % n;
            tank += gas[currentStation] - cost[currentStation];
            if (tank < 0) {
                possible = false;
                break;
            }
        }
        if (possible) {
            return i;
        }
    }
    return -1;
}

简单粗暴，但 O(N²) 的效率在 N 很大时会超时。

解法二：贪心算法 O(N) 这个问题的贪心解法有两个关键点：

全局判断：如果所有加油站的总油量 sum(gas) 小于总消耗 sum(cost)，那肯定无解，直接返回-1。
局部判断：
- 我们从 start = 0 开始，维护一个 currentTank 表示从start到当前站的油量结余。
- 遍历数组，不断更新currentTank。
- 如果在哪一站 i，currentTank 变成负数了，说明从 start 到 i 这段路是走不通的。更重要的是，从start到i之间的任何一个站作为起点，都走不到i+1。为什么？因为从start出发，我们是带着"正资产"（之前的油量结余）过来的，都走不通，那从中间某个站出发（资产更少），更不可能走通。
- 所以，一旦currentTank < 0，我们就把起点start更新为i+1，同时currentTank清零，重新开始计数。
- 由于我们一开始已经做了全局判断，保证了总油量是够的，所以这样找到的start一定是唯一的解。

public int canCompleteCircuit_2(int[] gas, int[] cost) {
    int totalTank = 0;
    int currentTank = 0;
    int startStation = 0;

    for (int i = 0; i < gas.length; i++) {
        totalTank += gas[i] - cost[i];
        currentTank += gas[i] - cost[i];

        // 如果当前油量不够了
        if (currentTank < 0) {
            // 说明从之前的 startStation 到 i 都不能作为起点
            // 新的起点候选是 i + 1
            startStation = i + 1;
            // 从新的起点开始，油箱清零
            currentTank = 0;
        }
    }

    // 如果总油量小于总消耗，无解
    return totalTank >= 0 ? startStation : -1;
}

这个解法只遍历一次，O(N)的复杂度，非常高效。

解法三：寻找最低点 O(N) 这是贪心算法的另一个角度。

计算diff[i] = gas[i] - cost[i]。问题变成：在diff这个环形数组中，找一个起点，使得从这个起点开始的任意长度的前缀和都 >= 0。
我们计算diff数组的累积和cummulativeSum。
如果整个环的累积和（也就是totalTank）是负的，肯定无解。
如果totalTank >= 0，解一定存在。这个解在哪里呢？
想象一下cummulativeSum的变化曲线。这个曲线的最低点的下一个位置，就是最佳的起点。
为什么？因为从最低点之后开始，所有的累积和都会是“爬坡”的，保证了油箱一直是“最满”的状态，能撑过之前的“亏损”路段。

public int canCompleteCircuit_3(int[] gas, int[] cost) {
    int n = gas.length;
    int totalDiff = 0;
    int minDiff = Integer.MAX_VALUE;
    int minIndex = 0;

    for (int i = 0; i < n; i++) {
        totalDiff += gas[i] - cost[i];
        if (totalDiff < minDiff) {
            minDiff = totalDiff;
            minIndex = i;
        }
    }

    if (totalDiff < 0) {
        return -1;
    }

    // 最低点的下一个点就是起点
    return (minIndex + 1) % n;
}

这个解法同样是O(N)，代码更简洁，思路也更巧妙。它抓住了问题的本质：找一个“油箱储量最低”的时刻，然后从这个时刻之后再出发。

15.3 组合列举的算法设计

组合问题不关心元素的顺序，{1, 2} 和 {2, 1} 是同一个组合。

15.3.1 子集

题目：给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。

解法一：回溯 (DFS) 经典的回溯模板。对于每个元素，我们都有“选”和“不选”两种选择。

backtrack(result, tempList, nums, start)
终止条件：无（因为任何中间状态都是一个合法的子集）。
循环：从start位置开始，向后遍历nums。
操作：
- 将当前元素加入tempList。
- 递归调用backtrack(..., i + 1)。
- 撤销选择，将当前元素从tempList中移除（回溯）。

import java.util.ArrayList;
import java.util.List;
public List<List<Integer>> subsets_1(int[] nums) {
    List<List<Integer>> result = new ArrayList<>();
    backtrack(result, new ArrayList<>(), nums, 0);
    return result;
}

private void backtrack(List<List<Integer>> result, List<Integer> tempList, int[] nums, int start) {
    // 每次进入都把当前路径加入结果集
    result.add(new ArrayList<>(tempList));
    for (int i = start; i < nums.length; i++) {
        tempList.add(nums[i]);
        backtrack(result, tempList, nums, i + 1);
        tempList.remove(tempList.size() - 1);
    }
}

解法二：迭代 这个思路很有趣。

开始时，结果集 result 只有一个空集 [[]]。
遍历nums中的每个数字num。
对于result中已有的每一个子集，都复制一份，并把num添加进去，然后把这些新生成的子集也加入result。

初始: result = [[]]
处理num=1: result中已有[]，新生成[1]，result变为[[], [1]]。
处理num=2: result中已有[], [1]，新生成[2], [1, 2]，result变为[[], [1], [2], [1, 2]]。
...以此类推。

public List<List<Integer>> subsets_2(int[] nums) {
    List<List<Integer>> result = new ArrayList<>();
    result.add(new ArrayList<>()); // 添加空集

    for (int num : nums) {
        int size = result.size();
        for (int i = 0; i < size; i++) {
            List<Integer> newSubset = new ArrayList<>(result.get(i));
            newSubset.add(num);
            result.add(newSubset);
        }
    }
    return result;
}

解法三：位运算 一个n个元素的集合，它的子集个数是2^n个。这2^n个子集，可以用n位二进制数来一一对应。从 0 到 2^n - 1，每个数都代表一个子集。比如 nums = [1, 2, 3]，n=3。

000 (0) -> {}
001 (1) -> {3}
010 (2) -> {2}
011 (3) -> {2, 3}
...
111 (7) -> {1, 2, 3} 第i位是1，就表示nums[i]被选中。

public List<List<Integer>> subsets_3(int[] nums) {
    List<List<Integer>> result = new ArrayList<>();
    int n = nums.length;
    int totalSubsets = 1 << n; // 2^n

    for (int i = 0; i < totalSubsets; i++) {
        List<Integer> subset = new ArrayList<>();
        for (int j = 0; j < n; j++) {
            // 检查第 j 位是否为 1
            if ((i & (1 << j)) != 0) {
                subset.add(nums[j]);
            }
        }
        result.add(subset);
    }
    return result;
}

15.3.2 子集 II

题目：与上一题类似，但nums中可能包含重复元素。返回的子集不能有重复。

解法一：回溯 + 排序剪枝 处理重复问题的关键是排序和剪枝。

先对nums进行排序，让相同的元素挨在一起。
在回溯的for循环中，加一个判断： if (i > start && nums[i] == nums[i-1]) continue; 这个判断的意思是，在当前这一层递归中，如果当前元素和上一个元素相同，并且上一个元素没有被使用（通过i > start来判断），那么就跳过当前元素。这可以避免产生重复的子集，比如对于[1, 2, 2']，我们只考虑用第一个2开头的组合，而跳过用第二个2'开头的组合。

public List<List<Integer>> subsetsWithDup_1(int[] nums) {
    List<List<Integer>> result = new ArrayList<>();
    Arrays.sort(nums); // 关键：排序
    backtrackWithDup(result, new ArrayList<>(), nums, 0);
    return result;
}

private void backtrackWithDup(List<List<Integer>> result, List<Integer> tempList, int[] nums, int start) {
    result.add(new ArrayList<>(tempList));
    for (int i = start; i < nums.length; i++) {
        // 关键：剪枝
        if (i > start && nums[i] == nums[i - 1]) {
            continue;
        }
        tempList.add(nums[i]);
        backtrackWithDup(result, tempList, nums, i + 1);
        tempList.remove(tempList.size() - 1);
    }
}

解法二：迭代 + 记录 在迭代法的基础上做修改。

同样需要先排序。
当遇到一个新数字num时：
- 如果它和前一个数字不同，那么就和普通子集问题一样，把它加入到result的所有现有子集中。
- 如果它和前一个数字相同，那么为了避免重复，我们只把它加入到上一轮刚刚生成的那些子集中。
这就需要记录上一轮新生成了多少个子集。

public List<List<Integer>> subsetsWithDup_2(int[] nums) {
    List<List<Integer>> result = new ArrayList<>();
    result.add(new ArrayList<>());
    Arrays.sort(nums);

    int lastSize = 0;
    for (int i = 0; i < nums.length; i++) {
        int start = 0;
        // 如果当前元素和上一个相同，只从上一轮新加的子集开始
        if (i > 0 && nums[i] == nums[i - 1]) {
            start = lastSize;
        }

        lastSize = result.size();
        for (int j = start; j < lastSize; j++) {
            List<Integer> newSubset = new ArrayList<>(result.get(j));
            newSubset.add(nums[i]);
            result.add(newSubset);
        }
    }
    return result;
}

解法三：先生成再用Set去重 最简单粗暴的方法，就是不管重复，用普通子集的生成方法，最后把结果放到一个Set里，自动去重。

import java.util.HashSet;
import java.util.Set;
// ...
// 1. 用 subsets_1 的回溯逻辑，但不加剪枝判断
// 2. 将所有生成的List加入 Set<List<Integer>>
// 3. 将Set转回 List<List<Integer>>
// 代码略，效率不高，但思路简单

这种方法可行，但效率较低，因为List的哈希计算和比较有开销，不推荐作为首选。

15.3.3 组合

题目：给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。

解法一：回溯 这是组合问题的标准模板。

backtrack(result, tempList, n, k, start)
终止条件：当tempList.size() == k时，找到一个组合，加入结果集。
循环：从start位置开始，遍历到n。
操作：加入数字 i，递归，回溯。

public List<List<Integer>> combine_1(int n, int k) {
    List<List<Integer>> result = new ArrayList<>();
    backtrackCombine(result, new ArrayList<>(), n, k, 1);
    return result;
}

private void backtrackCombine(List<List<Integer>> result, List<Integer> tempList, int n, int k, int start) {
    if (tempList.size() == k) {
        result.add(new ArrayList<>(tempList));
        return;
    }
    for (int i = start; i <= n; i++) {
        tempList.add(i);
        backtrackCombine(result, tempList, n, k, i + 1);
        tempList.remove(tempList.size() - 1);
    }
}

解法二：回溯 + 剪枝优化 在解法一的基础上，我们可以做一个很重要的剪枝。在 for 循环中，如果剩下的数字个数已经不够凑齐 k 个了，那就没必要再继续了。剩下的数字个数是 n - i + 1，我们还需要 k - tempList.size() 个数字。所以必须满足 n - i + 1 >= k - tempList.size()。整理得 i <= n - (k - tempList.size()) + 1。

private void backtrackCombine_Optimized(List<List<Integer>> result, List<Integer> tempList, int n, int k, int start) {
    if (tempList.size() == k) {
        result.add(new ArrayList<>(tempList));
        return;
    }
    // 剪枝：i 的上界可以收缩
    for (int i = start; i <= n - (k - tempList.size()) + 1; i++) {
        tempList.add(i);
        backtrackCombine_Optimized(result, tempList, n, k, i + 1);
        tempList.remove(tempList.size() - 1);
    }
}

这个剪枝能显著提高效率。

解法三：迭代生成 类似字典序的生成方式。

初始化第一个组合为 [1, 2, ..., k]。
循环生成下一个：
- 从右向左找到第一个可以增大的数 temp[i]（即temp[i] != n - k + 1 + i）。
- 将 temp[i] 加1。
- 它后面的数依次设为前一个数+1。
这个方法实现起来比较复杂，不如回溯直观。

// 迭代法实现较复杂，这里提供思路，实际编码中回溯法更常用。
// 1. 创建一个数组 temp，初始化为 [1, 2, ..., k, n+1]，最后一个是哨兵。
// 2. while(j < k) {
// 3.   把 temp[0...k-1] 加入结果
// 4.   j = 0; while(temp[j] + 1 == temp[j+1]) { temp[j] = j+1; j++; }
// 5.   if(j < k) temp[j]++;
// 6. }

15.3.4 找出所有子集的异或总和再求和

题目：给你一个数组 nums，返回 nums 中所有子集的异或总和的和。

解法一：生成所有子集再计算 O(N * 2^N) 最笨的方法：

用15.3.1的方法，生成所有子集。
遍历每个子集，计算它的异或和。
把所有异或和加起来。

public int subsetXORSum_1(int[] nums) {
    List<List<Integer>> subsets = subsets_1(nums); // 调用之前的方法
    int totalXorSum = 0;
    for (List<Integer> subset : subsets) {
        int subsetXor = 0;
        for (int num : subset) {
            subsetXor ^= num;
        }
        totalXorSum += subsetXor;
    }
    return totalXorSum;
}

简单但效率低。

解法二：回溯直接计算 O(2^N) 我们不需要真的把子集存起来。可以在回溯的过程中直接计算。

dfs(nums, index, currentXor)
- index: 当前处理到哪个数
- currentXor: 当前路径的异或和
- 递归到头（index == nums.length）时，返回 currentXor。
- 对于nums[index]，有两条路：
  - 不选它： dfs(nums, index + 1, currentXor)
  - 选它： dfs(nums, index + 1, currentXor ^ nums[index])
- 把两条路的结果加起来。

public int subsetXORSum_2(int[] nums) {
    return dfs(nums, 0, 0);
}

private int dfs(int[] nums, int index, int currentXor) {
    if (index == nums.length) {
        return currentXor;
    }
    // 不选 nums[index] 的路径贡献的和
    int notInclude = dfs(nums, index + 1, currentXor);
    // 选了 nums[index] 的路径贡献的和
    int include = dfs(nums, index + 1, currentXor ^ nums[index]);
    return notInclude + include;
}

这个方法避免了存储子集，效率更高。

解法三：数学/位运算 O(N) 这是本题的精髓。我们换个角度，不看每个子集，而是看每个比特位的贡献。

考虑第 i 个比特位。
只有当一个子集的异或和在第 i 位上为1时，它才会对总和贡献 2^i。
一个子集的异或和在第 i 位上为1，意味着这个子集中，第i位为1的数字出现了奇数次。
假设nums中，第i位为1的数有c个。那么在这c个数中，我们要选奇数个出来；而在剩下n-c个数中，可以任意选。
- 选c个中的1个：C(c, 1)
- 选c个中的3个：C(c, 3)
- ...
这样的组合数是 C(c, 1) + C(c, 3) + ... = 2^(c-1)。
对于剩下n-c个数，有2^(n-c)个子集。
所以，总共有 2^(c-1) * 2^(n-c) = 2^(n-1) 个子集的异或和在第i位上是1。
结论：只要nums中存在至少一个数在第i位上是1（即c > 0），那么第i位对总和的贡献就是 2^(n-1) * 2^i。
我们可以把所有nums中的数做一次或(|)运算，得到的结果totalOr中，所有为1的位，就是满足c>0的位。
所以最终答案是 totalOr * 2^(n-1)。

public int subsetXORSum_3(int[] nums) {
    int n = nums.length;
    if (n == 0) return 0;

    int totalOr = 0;
    for (int num : nums) {
        totalOr |= num;
    }

    return totalOr * (1 << (n - 1));
}

时间复杂度一步降到O(N)，这就是数学的魅力。

15.4 排列列举的算法设计

排列问题关心元素的顺序，{1, 2} 和 {2, 1} 是不同的排列。

15.4.1 全排列

题目：给定一个不含重复数字的数组 nums ，返回其所有可能的全排列。

解法一：回溯 + used数组 使用一个used布尔数组来标记哪些数字已经被使用过了。

backtrack(result, tempList, nums, used)
终止条件：tempList.size() == nums.length，找到一个排列。
循环：遍历所有数字i从0到n-1。
操作：如果nums[i]没被用过，就加入tempList，标记used[i]=true，递归，然后回溯（移除，标记used[i]=false）。

public List<List<Integer>> permute_1(int[] nums) {
    List<List<Integer>> result = new ArrayList<>();
    backtrackPermute(result, new ArrayList<>(), nums, new boolean[nums.length]);
    return result;
}

private void backtrackPermute(List<List<Integer>> result, List<Integer> tempList, int[] nums, boolean[] used) {
    if (tempList.size() == nums.length) {
        result.add(new ArrayList<>(tempList));
        return;
    }
    for (int i = 0; i < nums.length; i++) {
        if (!used[i]) {
            tempList.add(nums[i]);
            used[i] = true;
            backtrackPermute(result, tempList, nums, used);
            used[i] = false;
            tempList.remove(tempList.size() - 1);
        }
    }
}

解法二：回溯 + 交换 这个方法更巧妙，它不使用额外的used数组，而是在原数组上进行交换来生成排列。

backtrack(result, nums, start)
- start表示当前要确定哪个位置的元素。
- 终止条件: start == nums.length，说明所有位置都确定了。
- 循环：i从start到n-1。
- 操作：
  - 把nums[i]和nums[start]交换。这相当于把nums[i]“固定”在start位置。
  - 递归调用backtrack(..., start + 1)，去确定下一个位置。
  - 回溯：把nums[i]和nums[start]再换回来，恢复现场，以便for循环的下一次迭代。

import java.util.Collections;
public List<List<Integer>> permute_2(int[] nums) {
    List<List<Integer>> result = new ArrayList<>();
    List<Integer> numList = new ArrayList<>();
    for(int num : nums) numList.add(num);

    backtrackSwap(result, numList, 0);
    return result;
}

private void backtrackSwap(List<List<Integer>> result, List<Integer> numList, int start) {
    if (start == numList.size()) {
        result.add(new ArrayList<>(numList));
        return;
    }
    for (int i = start; i < numList.size(); i++) {
        Collections.swap(numList, start, i);
        backtrackSwap(result, numList, start + 1);
        Collections.swap(numList, start, i); // 回溯
    }
}

解法三：基于下一个排列算法 这是一种迭代的方法。

首先对数组排序，得到字典序最小的排列。
循环调用“下一个排列”算法，每次生成一个新的排列，直到回到最初的排列。这个方法依赖于Next Permutation算法的实现，该算法本身比较精巧。

// 先实现 nextPermutation 方法
public void nextPermutation(int[] nums) {
    // ... (实现细节参考 LeetCode 31. 下一个排列)
}

public List<List<Integer>> permute_3(int[] nums) {
    List<List<Integer>> result = new ArrayList<>();
    Arrays.sort(nums);

    // 计算阶乘，确定循环次数
    long count = 1;
    for (int i = 1; i <= nums.length; i++) count *= i;

    for (int i = 0; i < count; i++) {
        List<Integer> p = new ArrayList<>();
        for (int num : nums) p.add(num);
        result.add(p);
        nextPermutation(nums);
    }
    return result;
}

15.4.2 排列序列

题目：给出 n 和 k，返回 [1,2,3,...,n] 的所有全排列中，字典序第 k 个排列。

解法一：暴力生成再查找 TLE 用15.4.1的方法生成所有排列，排序，然后返回第k-1个。对于n=9，9! = 362880，还行。但n再大一点就崩了。

解法二：调用k-1次下一个排列 TLE 从[1,2,...,n]开始，调用k-1次nextPermutation函数。同样，k很大时会超时。

解法三：康托展开/阶乘进制数 O(N²) 这才是正解。

对于n个数的排列，以某一个数开头的排列有 (n-1)! 种。

比如n=4, k=9。4个数的全排列有4!=24种。
(4-1)! = 3! = 6。
第1-6个排列以1开头。
第7-12个排列以2开头。
k=9在7-12之间，所以第一个数肯定是2。
我们找到了第一个数2。现在问题变成了在剩下的{1, 3, 4}中找第9-6 = 3个排列。
新问题: n=3, k=3, 集合是{1, 3, 4}。
(3-1)! = 2! = 2。
第1-2个排列以1开头（在{1,3,4}中）。
第3-4个排列以3开头。
k=3在3-4之间，所以第二个数是3。
新问题：在{1, 4}中找第3-2=1个排列。
...以此类推。

算法流程：

预计算阶乘 factorial[0...n-1]。
创建一个列表 numbers 存储 [1, 2, ..., n]。
k要先减1，因为索引是从0开始的。
循环i从n到1：
- index = k / factorial[i-1]。这个index就是当前要选的数在numbers列表中的索引。
- 把numbers.get(index)加入结果。
- 从numbers中移除这个数。
- k = k % factorial[i-1]。更新k。

public String getPermutation(int n, int k) {
    int[] factorial = new int[n];
    factorial[0] = 1;
    for (int i = 1; i < n; i++) {
        factorial[i] = factorial[i - 1] * i;
    }

    List<Integer> numbers = new ArrayList<>();
    for (int i = 1; i <= n; i++) {
        numbers.add(i);
    }

    StringBuilder sb = new StringBuilder();
    k--; // convert to 0-based index

    for (int i = n; i >= 1; i--) {
        int index = k / factorial[i - 1];
        sb.append(numbers.get(index));
        numbers.remove(index);
        k %= factorial[i - 1];
    }

    return sb.toString();
}

这个方法直接计算出结果，时间复杂度是O(N²)，主要是因为numbers.remove是O(N)的。如果用更高级的数据结构可以优化到O(N log N)甚至O(N)。

顺序列举、组合列举、排列列举

15.2 顺序列举的算法设计

15.2.1 最大连续 1 的个数

15.2.2 数组中两元素的最大乘积

15.2.3 连续整数求和

15.2.4 电话号码的字母组合

15.2.5 数组中的最长山脉

15.2.6 长度最小的子数组

15.2.7 加油站

15.3 组合列举的算法设计

15.3.1 子集

15.3.2 子集 II

15.3.3 组合

15.3.4 找出所有子集的异或总和再求和

15.4 排列列举的算法设计

15.4.1 全排列

15.4.2 排列序列

推荐练习题

两数之和

组合总和 II

N 皇后

最大子数组和

完美数

平方数之和

顺次数

统计好三元组

统计特殊四元组

公因子的数目