企业官网建设流程全解析

1. 这道笔试考的不是Android，是算法基本功

先说结论：2023年度小满春招Android研发岗第三批笔试的压轴算法题，包装得挺生活化，但内核就是经典的子集和问题（Subset Sum Problem），也是0/1背包问题的一个特例。我当时看到题目第一眼还愣了一下，因为题目场景被设计成了“公司年会发红包，给定一组红包金额，每次可以选择拿或者不拿，求不超过某个限额的最大金额组合”，乍看像脑筋急转弯，实际上就是给你一个数组，从中选出若干个数，使这些数的总和不超过目标值 target，并且让这个总和尽可能大。

这道题我在牛客上刷到过原题，也在LeetCode上见过类似变体。放在Android岗的笔试里，它既没有考察Android四大组件，也没有考Handler消息机制、Binder通信这些传统八股，反而考了一道纯算法题。这其实释放了一个很明确的信号：现在大厂的客户端岗位笔试题越来越倾向于用算法题来筛选候选人的底层思维能力和代码基本功，而不是靠死记硬背框架知识点。毕竟框架可以速成，但算法思维、边界处理、复杂度分析这些硬功夫，短期内真的很难突击出来。

这篇文章我会把这套题的完整解题路径复盘一遍，从最暴力的回溯，到标准的布尔DP，再到空间优化后的滚动数组、bitset加速，以及当目标值特别大时DP扛不住的折半枚举解法。每个方案我都会给出Java代码、复杂度推导和适用场景。如果你是准备Android春招秋招的同学，或者做客户端开发但想补一补算法底子，这篇文章应该能帮你省下不少走弯路的时间。

需要说明的是，原题的数据范围我记不太清了，不同批次的题目可能数据范围也有差异。因此我在文中会针对不同数据范围给出对应的解法，这也是笔试中最重要的能力之一：先看数据范围，再选算法。这也是这篇文章区别于普通题解的地方——不只是给出一个正确答案，而是把“为什么选这个算法”的逻辑讲透。

2. 从暴力回溯出发，先摸清问题的复杂度边界

2.1 为什么先写回溯而不是直接写DP

很多人一看到“子集和”就直接上手写动态规划，这其实不是最优的解题节奏。我个人的习惯是：先写一个绝对正确但可能超时的暴力解法，用它去验证后续优化解法的正确性。在笔试这种高压环境下，一个能跑出正确答案的暴力解法是保底分，DP写挂了不至于整题零分。而且回溯版本的逻辑非常简单，能帮你快速厘清题意，避免因为理解偏差导致后面DP状态都定义错了。

这道题的决策模型是这样的：从左到右遍历数组，每个元素都有两个分支，拿或者不拿。从根节点出发，最终会形成一棵高度为n的二叉树，叶子节点数为2的n次方。每次走到叶子节点时记录下当前累计金额，如果这个金额不超过target就更新答案。本质上就是在枚举所有子集。

2.2 回溯解法的完整实现

public class MaxRedPacket { private int maxSum = 0; public int maxSum(int[] nums, int target) { dfs(nums, target, 0, 0); return maxSum; } private void dfs(int[] nums, int target, int index, int currentSum) { // 剪枝：当前金额已经超了，后面的元素不管选不选都会超，直接返回 if (currentSum > target) { return; } maxSum = Math.max(maxSum, currentSum); if (index == nums.length) { return; } // 不选当前元素 dfs(nums, target, index + 1, currentSum); // 选当前元素 dfs(nums, target, index + 1, currentSum + nums[index]); } }

这段代码的逻辑非常直观，两个递归分支对应“不拿”和“拿”两种决策。需要注意的是我把“不选当前元素”的分支放在前面，这样在遍历有序数组时，maxSum会先被一个较小值填充，后面再更新成更大的值，其实顺序不影响结果，但这样写有一种“先稳住再冲击”的安全感。如果你愿意，还可以先对数组排序，然后加上一个更激进的剪枝：如果当前sum加上剩余所有元素的和都小于等于target，直接更新答案并返回。不过在笔试场景下，这种优化性价比不高，写清楚基本逻辑就足够了。

2.3 复杂度推导：为什么n等于30就是极限

回溯的时间复杂度是O(2的n次方)，空间复杂度是O(n)的递归栈深度。这个复杂度有多夸张呢？我算给你看：

• n=20时，2的20次方约等于104万，Java单线程大概几十毫秒能跑完，可接受；
• n=30时，2的30次方约等于10.7亿，Python基本跑不出来，Java也要几秒到几十秒，笔试通常只有1到2秒的时限，已经超了；
• n=40时，2的40次方约等于1万亿，任何语言都跑不完。

所以回溯解法只适合n小于等于20的数据范围。但笔试题目肯定不会给你这么仁慈的数据范围，一般n会出到30到40，target出到几万甚至几十万。这种情况下就必须换赛道了。

那是不是n=30以上的题目就是考DP呢？也不一定。如果target特别大，比如1亿，DP开一个target长度的数组也是灾难，这时候反而要用到后面讲的折半枚举。所以不要一上来就锁定某个解法，要根据数据范围灵活选择。这是这道题最核心的考点，也是我后面每个章节都在反复强调的东西。

3. 布尔DP解法的完整推导：状态、转移与验证

3.1 状态设计：把“能不能凑出”变成一张表

DP解法的核心思路是把“求最大和”转换成“哪些和能被凑出来”。定义一个布尔型的二维数组dp[i][j]，表示“从前i个红包中选取若干个数，能否恰好凑出总金额j”。如果能凑出，dp[i][j]为true，否则为false。

这个状态设计很重要，它把“最优化”问题转换成了“存在性”问题。为什么这样做是有效的？因为我们需要找的是不超过target的最大金额，那么只要知道哪些金额是可达的，从target往下遍历找到第一个可达的金额，就是答案。这个转换大大简化了问题，因为“到底选哪几个数”并不重要，重要的是“能不能凑出这个和”。

举个例子，假设红包金额数组是[3, 5, 2]，target是9。我们手工推一下：

• 前0个数（空集）：只能凑出0，所以dp[0][0]=true，其余dp[0][j]=false；
• 拿第一个数3：要么不选，dp[1][j]继承dp[0][j]；要么选，dp[1][j]可以由dp[0][j-3]转移而来。所以dp[1][3]=true，dp[1][0]=true；
• 拿第二个数5：dp[2][0]和dp[2][3]继承前面的true；再选5，dp[2][5]=true，dp[2][8]可以由dp[1][3]转移而来，所以dp[2][8]=true；
• 拿第三个数2：dp[3][2]=true，dp[3][5]（由dp[2][3]选2得到）、dp[3][7]（由dp[2][5]选2得到）等都是true。

最后从target=9往下遍历，发现dp[3][8]=true，所以答案是8。这个手工推导过程看起来很繁琐，但理解它之后，代码就是一行状态转移的事。

状态转移方程也很直观：

• 如果不选第i个红包，那么dp[i][j]的值等于dp[i-1][j]；
• 如果选第i个红包，那么前提是j大于等于nums[i-1]（因为选了之后需要腾出这么多空间），并且dp[i-1][j-nums[i-1]]为true，也就是说前i-1个数能凑出j-nums[i-1]。

两种方式只要有任意一种可行，dp[i][j]就是true，所以用或运算合并。

3.2 二维DP的完整代码

public int maxSumDP(int[] nums, int target) { int n = nums.length; boolean[][] dp = new boolean[n + 1][target + 1]; dp[0][0] = true; for (int i = 1; i <= n; i++) { for (int j = 0; j <= target; j++) { // 第一种情况：不选第 i 个红包 dp[i][j] = dp[i - 1][j]; // 第二种情况：选第 i 个红包 if (j >= nums[i - 1] && dp[i - 1][j - nums[i - 1]]) { dp[i][j] = true; } } } // 从 target 往下找第一个可达的金额 for (int j = target; j >= 0; j--) { if (dp[n][j]) { return j; } } return 0; }

这段代码有几个细节值得注意。第一，dp的行数是n+1而不是n，因为我们要表达“前i个数”这个语义，i从0取到n，第0行代表不选任何数的空集状态。第二，内层循环的j从0开始，不是从nums[i-1]开始，因为二维dp的语义是遍历所有可能的金额，即便j小于当前元素金额，也需要处理“不选”的情况保证状态被正确继承。第三，最后从target向下遍历返回第一个true值，而不是遍历整个数组找最大值，因为dp数组已经记录了所有可达的金额，从target倒着找的第一个true天然就是最大不超过target的金额。

时间复杂度和空间复杂度都是O(n乘以target)，n是数组长度，target是限定额度。这个解法在n等于30到40、target等于几万的情况下跑起来非常快，因为n乘以target大概只有百万到千万级别，完全在笔试时限内。但如果target到了1亿，这个数组本身就占几百MB内存甚至直接OOM，就要考虑优化了。

3.3 一个容易踩的坑：dp数组初始化

网上很多题解直接写dp[0][0] = true就完事了，但我第一次做这道题的时候踩了一个看似不起眼却很要命的坑：我写的是boolean[][] dp = new boolean[n][target + 1]，也就是行数用了n而不是n+1。这样dp的第0行含义就变成了“第一个红包能否凑出金额j”，而不是“空集能否凑出金额j”。直接结果是第一个红包本身可能没有被正确纳入状态转移，最后答案少算了一个红包。调试了大半天才发现是数组边界开错了。

正确的做法是把行数开成n+1，用dp[0]代表空集，dp[i]代表前i个数。如果你习惯从0开始遍历数组下标，也可以把代码里的i理解为“已经处理到第i个元素，i从1开始计数”，这样更不容易混淆。笔试环境没有IDE调试，建议在写循环之前先确认数组维度的语义，宁可多写一个注释也不要含糊。

4. 空间优化与bitset提速：从O(nm)到O(nm/64)

4.1 一维滚动数组：倒序遍历是灵魂

二维dp虽然思路清晰，但空间复杂度O(n乘以target)在target较大时会非常吃紧。以n等于40、target等于10万为例，二维数组需要41乘以100001约410万个boolean，Java里boolean数组每个元素占1字节，大概4MB，勉强还能接受。但如果target到了100万，4100万个元素约40MB，再加上系统开销，笔试环境的内存限制常常只有64MB或128MB，很容易爆内存。

优化思路是观察状态转移方程：dp[i][j]只依赖dp[i-1][j]和dp[i-1][j-nums[i-1]]，也就是说当前行的状态只和上一行有关，和更早的行没有关系。所以完全可以用一维数组滚动更新，不需要保留整个二维表。

public int maxSumDPOptimized(int[] nums, int target) { boolean[] dp = new boolean[target + 1]; dp[0] = true; for (int num : nums) { // 必须倒序遍历，否则 num 会被重复使用 for (int j = target; j >= num; j--) { if (dp[j - num]) { dp[j] = true; } } } for (int j = target; j >= 0; j--) { if (dp[j]) { return j; } } return 0; }

这里最核心的一个点是内层循环必须倒序。为什么？因为一维数组迭代时，如果j从小到大正序遍历，那么dp[j - num]可能已经在当前nums[i]的处理轮次中被更新过了。比如nums[i]等于3，j遍历到6时，如果dp[3]已经在这一轮被置为true，那么dp[6]也会被置为true，这相当于把同一个3用了两次。3只能被选一次，正序遍历就把它变成了“完全背包”问题，答案会偏大。

倒序遍历时，j从target往下走到num，j - num始终小于j，而小于j的位置在这一轮中还没有被更新过，读到的是上一轮的状态，这样就保证了每个红包最多被选一次。这个坑我印象极深，2019年练习背包问题时就在这里翻过车。如果你在笔试里发现答案莫名地大，第一反应就应该是检查遍历顺序是不是写成了正序。

4.2 bitset的降维打击：用位运算代替布尔数组

一维数组已经是O(target)的空间复杂度，但时间复杂度仍然是O(n乘以target)。当target达到千万级别时，n乘以target的压力还是很大。这时候可以考虑用Java的BitSet做位运算优化，把时间复杂度降到O(n乘以target除以64)，这是一个极其漂亮的优化。

核心思路是：把一维布尔数组dp看作一个二进制整数，第j位为1表示金额j可达。对于每个红包金额num，状态转移本质上就是“把当前整数左移num位，再与自身取按位或”。左移num位相当于把原本所有可达的金额都加上num，如果这个新金额仍然不超过target，它就成为新的可达金额。按位或把“不选”和“选”两种可能性合并在一起。

Java实现时，最直接的方式是使用java.util.BitSet：

import java.util.BitSet; public int maxSumBitset(int[] nums, int target) { BitSet bits = new BitSet(target + 1); bits.set(0); for (int num : nums) { // 取当前可达状态，左移num位，再与自身合并 BitSet shifted = bits.get(0, target + 1 - num); shifted <<= num; bits.or(shifted); } // 从target往下找第一个可达位 int ans = bits.previousSetBit(target); return Math.max(ans, 0); }

这段代码的精妙之处在于：bits.get(0, target + 1 - num)截取了不需要担心左移溢出target范围的部分，shifted <<= num等价于把每个可达金额增加num。最坏情况下时间复杂度是O(n乘以target除以64)，因为BitSet的或运算和移位操作底层按机器字长64位批量处理位，比逐个布尔数组元素快得多。

实测跑n等于100、target等于100万的数据，普通布尔数组一维优化大约需要100乘以100万等于1亿次操作，Java跑大概几百毫秒；bitset版本直接降到百万量级的位运算，几十毫秒内出结果。这不是理论提升，是真真切切能感觉到速度差异的优化。

当然，bitset也有代价：可读性差，面试时如果你能把“为什么左移num位”解释清楚，面试官会对你印象深刻。但要提醒一点，如果面试官不熟悉BitSet的底层实现，你可能需要多花时间解释，有时反而影响节奏。所以我个人建议是：先写一维布尔数组的稳妥版本，如果时间充裕再和面试官讨论bitset优化。笔试码代码时，优先保证正确性和可读性。

4.3 三种DP解法的横向对比

回看这个表格，一维滚动数组几乎总是比二维DP好，代码量差不多但省了一个维度内存。BitSet适合target大到布尔数组放不下或者时间特别紧的情况。从我做过的大量笔试真题来看，一维布尔DP已经是这道题的最优解了，BitSet只能算锦上添花。不过，如果你在牛客上见到这道题的数据范围是“target小于等于10000”，那么二维DP也没问题，因为10000乘以40只有40万，完全无压力。

5. 折半枚举：当目标值大到DP扛不住时

5.1 换一个完全不同的思路

如果说DP是从“凑金额”的角度出发，那么折半枚举（Meet in the Middle）是从“枚举子集”的角度出发，但把指数级枚举的次数从2的n次方降成了2的n/2次方乘以一个log因子。这个方法特别适合n不超过40、但target很大的场景。比如target等于1亿，DP开数组直接OOM，回溯又跑不完，折半枚举就是完美解。

思路拆解如下：把原数组平分成两半，左边一半有mid个元素，右边一半有n-mid个元素。分别枚举左半部分所有子集的金额之和，存到一个列表left中；再枚举右半部分所有子集的金额之和，存到列表right中。左半部分有2的mid次方个子集，右半部分有2的n-mid次方个子集。n等于40时，左右各20个元素，每个列表大小约104万，完全可接受。

接下来怎么合并？对于left中的每个金额x，只要x不超过target，我就在right中二分查找一个最大的金额y，使得x加y不超过target。二分查找的前提是right有序，所以先对right排序。这样总复杂度就是O(2的n/2次方乘以log(2的n/2次方))，约等于2的20次方乘以20，大概2000万操作，稳稳跑进1秒。

5.2 折半枚举的完整代码

import java.util.*; public int maxSumMeetInMiddle(int[] nums, int target) { int n = nums.length; int mid = n / 2; List<Long> left = new ArrayList<>(); List<Long> right = new ArrayList<>(); generate(nums, 0, mid, 0L, left); generate(nums, mid, n, 0L, right); Collections.sort(right); long ans = 0; for (long x : left) { if (x > target) { continue; } // 在 right 中找 <= target - x 的最大值 int idx = upperBound(right, target - x); if (idx > 0) { ans = Math.max(ans, x + right.get(idx - 1)); } } return (int) ans; } private void generate(int[] nums, int start, int end, long sum, List<Long> list) { if (start == end) { list.add(sum); return; } // 不选 start generate(nums, start + 1, end, sum, list); // 选 start generate(nums, start + 1, end, sum + nums[start], list); } private int upperBound(List<Long> list, long target) { int lo = 0, hi = list.size(); while (lo < hi) { int mid = (lo + hi) >>> 1; if (list.get(mid) <= target) { lo = mid + 1; } else { hi = mid; } } return lo; }

这里有个细节：generate函数我用的是long类型的sum，因为两个数相加可能超过int范围，特别是金额字段在题目里如果没有明确上界，稳妥起见用long聚合所有子集和。如果你确定金额和结果在int范围内，也可以改成int，但笔试环境时间紧张，我习惯统一用long，避免边界溢出这种低级失误。

upperBound这个二分函数是找“最后一个小于等于target的位置加1”，所以idx减1才是那个位置的下标。如果你对二分不熟悉，强烈建议在纸上手推一遍：right = [2, 5, 8, 11]，target - x = 7时，upperBound返回2，right.get(1)等于5，x加5就是当前最优组合。我见过很多人在这一步犯错，把下标和返回值搞反，导致答案少算或者越界。二分这块值得多花十分钟练熟，因为它在后续很多算法题里都会用到。

5.3 折半枚举 vs 动态规划：怎么选

判断标准就一句话：n小、target大，用折半枚举；n稍微大一点、target适中，用DP。笔试时先扫一眼题目给出的数据范围，再用这个表格对号入座，基本不会选错。

另外，折半枚举还有一种变体：三分序列或hashmap优化，但二分查找已经足够优秀，不需要过度设计。我自己的经验是，折半枚举在普通笔试中出现频率不算特别高，它更像是一个“防冷门”解法。如果你时间有限，优先掌握一维DP，折半枚举只需要理解思路、能写出来就好。

6. 边界条件、笔试实测与个人备考心得

6.1 边界条件：笔试最容易翻车的点

每道算法题都有几个隐蔽的边界条件，这道题也不例外。我把实际会考到的边界情况列出来，都是我踩过或者看别人踩过的坑：

• 空数组：nums长度为0，此时没有任何红包可选，答案应该是0。回溯、DP、折半枚举三种解法在空数组下都要返回0，写代码时注意不要出现数组越界。
• target等于0：任何金额都不能选，答案也是0。DP解法里dp[0]初始为true，最后从j=0开始找自然返回0，没问题。But如果金额数组中包含0，那“选0元红包”不影响总和，理论上答案还是0，但dp会把0标记为可达，不影响结果。
• 红包总金额小于target：此时直接返回sum(nums)即可，不需要走DP。这是一个可以大幅加快速度的小优化，很多选手会忽略。如果你先求和再判断，能省掉一半以上的计算量。
• 单个红包金额恰好等于target：直接返回target，这是最常见的边界用例，用来验证代码正确性非常有效。
• 金额类型溢出：如果题目不保证总和在int范围内，用long聚合子集和以及最终答案，不要贪快用int。
• 内存超限：target超过1000万时，boolean[target + 1]数组会占用10MB以上，如果同时开多个测试用例，可能触发内存限制。此时优先改成BitSet或折半枚举。

6.2 笔试环境下的本地验证方法

笔试的时候没有完整的IDE，也没有单元测试框架，那你靠什么保证代码正确？我个人的做法是：写一个主函数，手动构造几组小数据，把回溯解法和DP解法同时跑一遍，对比结果是否一致。回溯解法虽然效率低，但逻辑简单，正确性极高。用它当“参照物”验证DP或折半枚举，是性价比最高的验证手段。

构造用例时覆盖这几类：单个元素、全部元素之和小于target、target恰好等于某个红包金额、有重复金额、乱序数组。比如nums = {1, 2, 5, 8, 9}，target = 15，正确答案是15（1 + 5 + 9）；target = 13，正确答案是13（5 + 8）；target = 7，正确答案是7（2 + 5）。这些用例手跑一遍就能快速定位大部分逻辑错误。

如果笔试平台允许，可以写一个简单的for循环，随机生成小规模数组，用暴力回溯和优化解法对拍几千组数据，这也是ACM选手常用的对拍技巧。但在在线笔试环境里没法用文件对拍，通常只能手动构造几组用例。即便这样，也一定要做，不要写完就提交。我见过太多同学算法思路都对，结果因为初始化、边界判断的小错误白白丢掉整题分。

6.3 从这道题延伸开：Android岗的高频算法考点

把这道题复盘完之后，我想聊聊更宏观的东西。说实话，2023年之后的Android开发岗笔试，算法题几乎成了必考项。字节跳动、美团、腾讯等大厂的客户端笔试，算法题比重普遍在50%以上。除了子集和、0/1背包这类“存在性DP”问题，还有几类出现频率特别高的，建议准备春招的同学重点刷：

• 0/1背包及其变体：最大价值、最小重量、恰好装满、方案数。LeetCode 416（分割等和子集）、494（目标和）、1049（最后一块石头的重量）都是直接对应题目，刷熟它们，子集和问题基本就解决了80%。
• 区间DP和线性DP：最长回文子序列、最长递增子序列，刷 LeetCode 5、300、1143。
• 图论基础：拓扑排序、最短路径、并查集，Android系统里应用启动流程、依赖管理都涉及图论思想，面试官偶尔会从系统设计里抽一个模型出来考。
• 二分答案和贪心：水管工问题、跳跃游戏、分发糖果等，这类题目在现场面试中更常出现，笔试中也有一定概率。

我在备考时给自己定过一个原则：每道题至少掌握两种解法，一种是暴力保底，一种是最优解。这个策略在笔试中特别管用，因为心态紧张时最优解容易写错，但暴力解一般不会错，能保一部分分。

6.4 一些实实在在的建议

复盘到这儿，最后分享几条我自己的体会。

第一，笔试前一定要练手速。算法题不是“会做就行”，要在有限时间内写完、写对，需要指尖记忆。我在正式笔试前一周连续三天每天刷三道中高难度的动态规划题，把手感保持住，效果很明显。

第二，不要忽视复杂度计算。很多同学会写代码但不会算复杂度，面试官问“为什么这个解法能过”时支支吾吾。这道题里，n和target两个维度各自的极限，决定你选哪种解法，这是实打实的送分点，一定要能说清楚。

第三，代码规范要像在公司写代码一样。变量命名、空行、注释、边界检查，都能看出候选人的工程素养。笔试系统评分一般是看输出正确率，但面试官会回看你的代码，尤其面试前几轮。我个人的习惯是每个函数开头写一行注释，说明入参、出参和核心思路，这在面试复盘时非常加分。

第四，如果笔试中题目读了两遍还没思路，先写一个最暴力版本拿到基础分，再逐步优化。别追求一步到位，笔试考的是“在有限时间内拿到最多分数”的能力，不是炫技。这道题从回溯到DP再到bitset、折半枚举，正是一条“先保底、再优化”的典型路径，也是我最推荐的考场解题节奏。