教程【免费下载链接】Learn-Algorithms算法学习笔记项目地址https://gitcode.com/gh_mirrors/le/Learn-Algorithms点击查看免费下载导读本文以 5.2 数列-nsum问题.md 为主线系统梳理算法面试与刷题中高频出现的「数列求和」类问题从最基础的两数之和twoSum到有序数组双指针夹逼、最大子数组和最大字段和、连续正数序列、滑动窗口、背包式组合求和、贪心找零、子集等和划分再到 n 个骰子点数概率与数组均分问题。读完本文你将掌握暴力枚举、哈希表、双指针、滑动窗口、动态规划、贪心六大解题范式并能直接对照仓库 codes 下的 C 语言实现进行验证与实战训练。1. 经典开篇数组里找出和为 target 的两个数这是 nSum 问题的元问题也是 LeetCode 第 1 题的原型。给定整数数组nums与目标值target要求返回两个数对应下标使得nums[i] nums[j] target。1.1 暴力解法O(N²) 双重循环最直观的思路是枚举所有下标对(i, j)逐一比较两数之和是否等于target。原文档给出的 Java 实现如下class Solution { public int[] twoSum(int[] nums, int target) { int res[] new int[2]; for(int i 0; i nums.length; i){ for(int j i 1; j nums.length; j){ if(nums[i] nums[j] target){ res[0] i; res[1] j; break; } } } return res; } }时间复杂度O(N²)双层循环穷举所有组合。空间复杂度O(1)仅使用常数级辅助空间。适用场景数据规模极小如 N 100或笔试手写验证思路时可作为保底方案面试中通常需要进一步优化。1.2 哈希表两遍扫描O(N) 时空互换把「查找差值」的 O(N) 内层循环换成哈希表的 O(1) 查询是典型的空间换时间。原文档给出的思路是两遍扫描第一遍把所有元素值映射到下标第二遍逐个元素检查target - nums[i]是否存在于表中。class Solution { public int[] twoSum(int[] nums, int target) { int res[] new int[2]; MapInteger, Integer map new HashMap(); for(int i 0; i nums.length; i){ map.put(nums[i], i); } for(int i 0; i nums.length; i){ int temp target - nums[i]; if(map.containsKey(temp) map.get(temp) ! i){ res[0] map.get(temp); res[1] i; } } return res; } }要点说明map.get(temp) ! i用于排除「同一个元素被使用两次」的情况——例如nums [3,3]、target 6时第二遍扫描下标 0 会查到自己必须通过下标判断跳过。可进一步优化为一遍扫描边遍历边把(nums[i], i)写入哈希表同时检查target - nums[i]是否已存在由于后写入的元素尚未入表天然避免了重复使用自身的问题。时间复杂度 O(N)、空间复杂度 O(N)适用于数组未排序、需要返回下标而非元素值的场景。哈希表思路可扩展到「找最接近 target 的两个数」「找三个数之和」等变体仓库海量数据处理示例 most_visit_ip.c 展示了哈希分桶思想在「一亿个 IP 中统计最高频 IP」这类大数据场景下的应用——按i 27将 IP 哈希映射到 32 个临时文件再对每个分片统计是「哈希映射 分而治之」的经典组合。2. 和为 N1 的数对值域已知的计数问题题目一个整数数列元素取值可能是1~NN 是较大的正整数中的任意一个数且相同数值不会重复出现。设计算法找出满足「两数和等于N1」的数对个数要求复杂度最好为O(N)若是 O(N²) 则不得分。分析由于元素互不重复且取值范围已知每一对数都形如(k, N1-k)。枚举所有数对后N1可以拆出【1, N】【2, N-1】【3, N-2】...等对称结构——原文档给出的示例是输入 15输出【1,14】【2,13】【3,12】...。原文档给出的函数原型为int print_sequence_sum(int n)解题要点若能以 O(N) 时间将元素是否出现标记进布尔数组哈希思想则对每个k ∈ [1, N]检查k与N1-k是否同时存在即可整体 O(N)。若元素本身可排序也可用「双指针夹逼」在 O(N) 内完成计数见第 3 节。核心考点在于利用值域已知 元素互异的约束避免 O(N²) 枚举。3. 有序数组找出和为 m 的两个数双指针夹逼 O(N)题目输入一个已经升序排序的数组和一个数字 m在数组中找两个数使它们的和正好为 m要求时间复杂度O(N)。若有多对满足条件输出任意一对即可。例如输入数组【1、2、4、7、11、15】和数字 15由于41115因此输出 4 和 11。原文档给出的函数签名//返回0找到返回-1没找到 int findaddends(int *data,int length,int sum,int *a,int *b);3.1 先想到的二分查找方案 O(N·logN)因为数组升序对每个元素data[i]用二分查找sum - data[i]每次查找 O(logN)整体 O(N·logN)。原文档明确指出了这条思路「数组升序排列查找可用二分查找时间复杂度 O(logn)这样问题就变成了找其中一个加数的问题复杂度为 NlogN」*。3.2 更妙的两端向中间扫描 O(N)巧妙解法用两个指针分别指向数组两端逐步向中间靠拢data[left] data[right] m找到返回data[left] data[right] m和偏小left增大加数data[left] data[right] m和偏大right--减小加数。由于数组有序指针每次移动都保证「不漏解」整体仅需 O(N) 次比较空间 O(1)。伪代码骨架int findaddends(int *data, int length, int sum, int *a, int *b) { int left 0, right length - 1; while (left right) { if (data[left] data[right] sum) { *a data[left]; *b data[right]; return 0; } else if (data[left] data[right] sum) { left; } else { right--; } } return -1; }适用前提数组必须已升序。这一「有序性 → 双指针」的套路是后续滑动窗口、三数之和、盛水容器等问题的基石。4. 求子数组的最大和最大字段和动态规划 O(N)题目输入一个整型数组有正数也有负数数组中连续的一个或多个整数组成一个子数组求所有子数组和的最大值要求时间复杂度 O(N)。例如输入1, -2, 3, 10, -4, 7, 2, -5和最大的子数组为3, 10, -4, 7, 2输出 18。4.1 蛮力法三重循环 O(N³)枚举所有起点i、终点j再累加fmax(i,j)求最大值。三重循环复杂度 O(N³)仅适合极小规模数据或用于验证正确性。4.2 动态规划Kadane 算法O(N)原文档给出的 C 实现用maxendinghere保存「以当前位置结尾的连续子数组的最大和」一旦累加值小于 0 就清零重来max记录历史最大值int maxSumOfVector(int *data,int length){ int max0; int maxendinghere 0; if(dataNULL || length0){ return 0; } for(int i0;i length; i){ maxendingheredata[i]; if(maxendinghere0){ maxendinghere0; continue; } if(maxendingheremax){ maxmaxendinghere; } } return max; }要点分析状态转移思想maxendinghere max(maxendinghere data[i], data[i])。原文档实现中「清零」的写法等效于当累计和为负时丢弃之前的部分——因为负前缀只会拖累后续子数组。边界情况若数组全为负数maxendinghere每次都被清零最终返回 0。若要支持「最大子数组和允许为负」应把max初始化为data[0]并改为maxendinghere max(maxendinghere data[i], data[i])的标准 Kadane 写法。时间复杂度 O(N)空间 O(1)是动态规划入门的最经典例题之一。完整思路还可参见仓库 动态规划.md 与 分治算法.md分治版可做到 O(N·logN)。5. 和为 n 的连续正数序列双指针滑动 O(N)题目输入一个正数 n输出所有和为 n 的连续正数序列。例如输入 15由于12345 456 78 15输出 1-5、4-6 和 7-8 三个序列。原文档给出函数原型print_continuous_sequence_sum(int n)5.1 思路一枚举法 O(N²)从 1 开始累加到等于 n再从 2 开始……直到n/21。每一轮逐步比较累加和与 n复杂度 O(N²)。实现简单但显然不满足大规模数据的要求。5.2 思路二滑动双指针 O(N)滑动窗口思想用small和big两个指针夹出一个窗口sum维护窗口内元素和sum nsmall前移窗口收缩sum - smallsum nbig前移窗口扩张sum bigsum n记录一组[small, big]继续移动指针寻找下一组。该思路的原文档描述为「a[small,big] sum[small,big]N small 往前移动否则big 往前移动。O(N) 复杂度搞定」。仓库中的 print_continuous_sequence_sum.c 给出了该思路的完整可运行 C 实现#include stdio.h //打印和为n的2个值 void print_continuous_sequence_sum(int n){// n1,2 int small1; int big2; int sum smallbig; while(smallbig bign/21){ if (sumn){ printf(%d ,%d\n,small,big); } while(sumn){ sum-small; small; if (sumn){ printf(%d, %d\n,small,big); } } big; sumbig; } } int main(int argc, char const *argv[]){ print_continuous_sequence_sum(115); return 0; }实现细节说明终止条件big n/2 1连续序列至少包含两个数且最大起点不会超过n/2否则单元素就可能超过 n天然剪枝。small big保证序列长度 ≥ 2连续正数序列的最小长度是 2题目如允许单个元素则 n 本身也是一组解需按题意调整。该实现以「发现一组解」时打印为设计目标若要求输出全部解可在sum n后同步small、sum - small继续向后滑动。时间复杂度 O(N)small与big均单向移动总步数 O(N)。仓库同目录下的 longest_continuious_number.c在字符串中找出最长连续数字串与本例同属双指针/单次扫描范式可对照练习。6. 连续子数组和为 m滑动窗口求「恰好等于」题目数组[2,3,1,2,4,3]求所有和为 7 的连续子数组结果为[1,2,4]与[3,4]。6.1 暴力遍历枚举所有起点与终点并累加比较复杂度 O(N²)。6.2 滑动窗口左指针 右指针原文档给出的核心逻辑骨架if sumk rlen{ sumarr[r] r }else{ sum - arr[l] l }注意上述骨架是「单指针滑动 收缩」的简化示意。完整可靠的实现应写成标准双指针循环int left 0, sum 0; for (int right 0; right len; right) { sum arr[right]; // 窗口右边界扩张 while (sum k left right) { // 窗口左边界收缩 sum - arr[left]; left; } if (sum k) { // 记录 arr[left..right] 为一组解 } }要点该算法要求数组元素均为正数窗口和随右指针单调不减才能保证「和大了收缩左边界」的逻辑成立若数组含负数滑动窗口失效需改用前缀和 哈希表O(N)。时间复杂度 O(N)右指针遍历一遍左指针整体最多移动 N 次。与第 5 节「连续正数序列」本质相同是同一滑动窗口范式的一体两面。7. 和为 m 的组合从 1~n 中选数背包型动态规划题目输入两个整数 n 和 m从数列1, 2, 3, ..., n中随意取几个数使其和等于 m要求列出所有可能组合。例如n10, m25。原文档给出函数原型print_sum_detials(int n, int sum)并明确提示用动态规划类似背包问题给出了四步法框架划分问题把「从 1~n 中选若干数求和为 m」划分为「含 n」与「不含 n」两个子问题选择状态以(当前可选最大值 i, 剩余和 s)描述子问题状态转移方程选 isolve(i-1, s-i)并记录 i不选 isolve(i-1, s)边界s 0时输出一组解i 0 || s 0时回溯。规划方程/递归边界当s 0输出当s 0或i 1剪枝返回。以n10, m25为例的递归回溯实现骨架void print_sum_detials(int n, int sum, int *path, int depth) { if (sum 0) { /* 输出 path[0..depth-1] */ return; } if (n 0 || sum 0) return; // 不选 n print_sum_detials(n - 1, sum, path, depth); // 选 n path[depth] n; print_sum_detials(n - 1, sum - n, path, depth 1); }要点每个数字至多用一次等价于0/1 背包的「选/不选」决策也可用 DP 表dp[i][s]记录「前 i 个数能否凑出和 s」。若要输出全部组合递归回溯DFS天然适合若只求「有多少种方案」二维 DP 或一维滚动数组即可。更一般的变体——给定正整数数组求若干元素和为 m 的所有组合——同样适用本范式。8. 钞票找零最少张数贪心算法题目钞票面值 100、50、20、10、5、2、1 元支付 628 元问最少需要几张钞票。思路贪心算法——每次优先使用面值最大且不超过剩余金额的钞票628 → 6 张 100剩 28→ 1 张 20剩 8→ 1 张 5剩 3→ 1 张 2剩 1→ 1 张 1共61111 10 张。关键讨论点本组面额100/50/20/10/5/2/1具有「大面额是相邻小面额的整数倍」结构贪心策略在此保证最优反例提醒若面额改为[1, 3, 4]且需凑 6 元贪心选 411 共 3 张而最优解33只需 2 张——贪心只在特定货币体系下成立通用场景应改用动态规划完全背包dp[s] min(dp[s - coin] 1)。9. 若干个数之和与 M 最为接近题目给定一个按升序排列的实数数组从数组中找出若干个数使它们的和与 M 最为接近描述算法并给出复杂度。分析若「若干个数」指任意数量该问题本质是subset-sum 类问题NP 完全只能接受近似解或指数级搜索可用动态规划在O(N·M)和值整数化内求「最接近 M 的可行和」实数场景通常退化为回溯剪枝或贪心近似。若「若干个数」特指两个数且数组有序则第 3 节的双指针夹逼略作改造即可维护best与当前两数和按与 M 的绝对差更新最优解复杂度 O(N)。若「若干个数」指连续子段则类似第 4 节最大子数组和的变体Kadane 思想扩展。原文档此处仅给出题目与复杂度要求未给出标准答案——这正是面试中考察「先澄清约束再选择算法」能力的典型题目答题时应先与面试官确认取值个数与元素性质。10. 数组能否分割成两个和相等的子集LeetCode 416题目给定一个只包含正整数的非空数组判断能否分割成两个子集使两个子集的元素和相等LeetCode 416难度中等。思路动态规划。推导设数组总和为total。两个子集和相等 ⇒ 每个子集和必为total/2故total必须为偶数否则直接返回 false。问题转化为能否从数组中选出若干元素恰好凑出total/2——即 0/1 背包可行性问题。DP 定义dp[s]表示「能否凑出和 s」dp[0] true对每个元素num倒序更新dp[s] dp[s] || dp[s - num]倒序保证每个元素至多用一次。bool canPartition(int *nums, int numsSize) { int total 0; for (int i 0; i numsSize; i) total nums[i]; if (total % 2 ! 0) return false; int target total / 2; bool *dp calloc(target 1, sizeof(bool)); dp[0] true; for (int i 0; i numsSize; i) { for (int s target; s nums[i]; s--) { dp[s] dp[s] || dp[s - nums[i]]; } } return dp[target]; }时间复杂度 O(N·target)空间可压缩为一维数组 O(target)。11. n 个骰子的点数概率题目把 n 个骰子扔在地上所有骰子朝上一面的点数之和为 S输入 n打印 S 的所有可能取值出现的概率。例如n1时取值为【1,2,3,4,5,6】每个概率1/6n2时取值为【2~12】。思路动态规划——把问题分解为「前 k 个骰子的和分布」递推到「前 k1 个骰子」。状态dp[k][s]表示 k 个骰子掷出和为 s 的方案数转移dp[k][s] sum(dp[k-1][s - d])其中d ∈ [1,6]为第 k 个骰子的点数初始化dp[1][1..6] 1概率方案数除以总数6^n。// dp[k][s]k 个骰子掷出和为 s 的方案数 for (int k 2; k n; k) { for (int s k; s 6 * k; s) { dp[k][s] 0; for (int d 1; d 6 d s; d) { dp[k][s] dp[k - 1][s - d]; } } } // S 的取值范围为 [n, 6n]概率 dp[n][S] / 6^n时间复杂度 O(n²·6)空间可滚动为一维数组。该题与「和为 m 的组合」「子集划分」同属计数型动态规划家族体现了「划分问题 → 定义状态 → 写出转移方程」的统一方法论。12. 将整数数组分成 m 份使各份和相等求 m 最大值题目一个整数数组长度为 n将其分为 m 份使各份的和相等求 m 的最大值。例如{3, 2, 4, 3, 6}分成 1 份{3,2,4,3,6}m1分成 2 份{3,6}与{2,4,3}m2分成 3 份{3,3}、{2,4}、{6}m3所以 m 的最大值为 3。分析若 m 份和相等则total % m 0且每份和为total / m。因此从大到小枚举 m从数组长度向下尝试第一个可行解即最大值。判定「能否恰好分成 m 份每份和为 target」是一个组合划分判定问题可用 DFS 回溯 剪枝将数组降序排列以加速、维护已满分组数等复杂度指数级实际靠剪枝支撑。该题是「子集和相等划分」第 10 节的推广第 10 节是 m2 的特例可用 DP 精确求解m2 时通常只能回溯搜索。13. 六大解题范式速查范式适用场景时间复杂度代表题目本文节次暴力枚举数据规模极小、验证思路O(N²)~O(N³)1.1 两数之和、4.1 最大子数组和、6.1 连续子数组哈希表未排序数组、需返回下标O(N) 时间 / O(N) 空间1.2 两数之和、2 和为 N1双指针夹逼已排序数组、求两数和O(N)3 有序数组和为 m、9 最接近 M 的两数滑动窗口连续子段、元素为正O(N)5 连续正数序列、6 连续子数组和为 m动态规划组合/计数/最值、子问题重叠视状态而定4 最大子数组和、7 和为 m 的组合、10 子集划分、11 骰子概率、12 均分数组贪心局部最优即全局最优需证明O(N)8 钞票找零14. 仓库延伸阅读完整问题列表与代码9 Algorithms Job Interview/5.2 数列-nsum问题.md与其对应的 codes 目录数列问题相邻专题5.1 数列-排序.md、5.3 数列-交并集.md、5.4 数列-查找.md算法方法论动态规划.md、贪心算法.md、分治算法.md、回溯法.md、迭代法.md数据结构基础数组.md、HashMap in Java.md可运行源码示例print_continuous_sequence_sum.c连续正数序列直接gcc编译运行、longest_continuious_number.c双指针练习、most_visit_ip.c哈希分桶大数据统计。实战建议刷题时先判断数据规模与数组是否有序据此在「哈希表 / 双指针 / 滑动窗口 / 动态规划」四条主路径中快速定位每道题先用暴力法验证正确性再按复杂度要求逐级优化并随手用仓库中的 C 源码对照调试这是从「看懂解法」进阶到「写出解法」最有效的训练方式。赞分享教程【免费下载链接】Learn-Algorithms算法学习笔记项目地址https://gitcode.com/gh_mirrors/le/Learn-Algorithms点击查看免费下载相关推荐掌握高效音频转写的5大进阶技巧Buzz离线转录工具深度解析掌握高效音频转写的5大进阶技巧Buzz离线转录工具深度解析 在当今数字化时代音频内容处理已成为内容创作者、研究人员和专业人士的日常需求。然而传统在线语音识教程如何免费破解百度网盘SVIP下载速度限制这个开源插件让下载速度飙升70倍如何免费破解百度网盘SVIP下载速度限制这个开源插件让下载速度飙升70倍 凌晨两点你盯着百度网盘那根纹丝不动的进度条一个9GB的安装包速度稳定在100K逆向工程插件系统Learn-Algorithms项目全解析15大经典算法实战指南Learn Algorithms项目全解析15大经典算法实战指南 项目概述 Learn Algorithms是一个全面的算法学习笔记项目涵盖了从基础数据结构教程上一篇从0开始的gh_mirrors/la/lang源码阅读核心模块解析下一篇Grayscale主题深度评测为什么它是2023年最受欢迎的Bootstrap单页模板创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考