华为OD机试 - 符合条件的元组个数 - 递归、双指针（Java 新系统 100分）

华为OD机试 新系统 题库疯狂收录中刷题点这里专栏导读本专栏收录于《华为OD机试JAVA真题》。刷的越多抽中的概率越大私信哪吒备注华为OD加入华为OD刷题交流群每一题都有详细的答题思路、详细的代码注释、3个测试用例、为什么这道题采用XX算法、XX算法的适用场景发现新题目随时更新全天CSDN在线答疑。一、题目描述给定一个整数数组 nums一个数字k一个整数目标值 target请问nums中是否存在 k个元素使得其相加结果为target请输出所有符合条件且不重复的k元组的个数数据范围• 2 ≤ nums.length ≤ 200• -10^9 ≤ nums[i] ≤ 10^9• -10^9 ≤ target ≤ 10^9• 2 ≤ k ≤ 100二、输入描述第一行是nums取值2 7 11 15第二行是k的取值2第三行是target取值9三、输出描述输出第一行是符合要求的元组个数1补充说明[2,7]满足输出个数是1四、测试用例测试用例11、输入-1 0 1 2 -1 -4302、输出23、说明符合条件的唯一元组有 [-1, -1, 2] 和 [-1, 0, 1]所以结果是 2。测试用例21、输入2 7 11 15292、输出13、说明只有 [2, 7] 满足条件所以结果是 1。五、解题思路排序把 nums 升序排列后续可以直接跳过重复值并用双指针处理 2Sum。递归降维当 k 2 时枚举当前层的一个数 nums[i]然后在右侧区间里继续找 k-1 个数。同一层里如果 nums[i] nums[i-1]直接跳过避免重复元组。双指针终止当 k 2 时在有序数组里用左右指针统计唯一配对个数。剪枝优化当前最小可能和都大于 target后面只会更大直接 break。当前最大可能和都小于 target当前值不够大直接 continue。六、Java算法源码publicclassOdTest{publicstaticvoidmain(String[]args){ScannerscnewScanner(System.in);// 读取第一行nums 数组Stringline1readNonEmptyLine(sc);if(line1null){return;}// 读取第二行kStringline2readNonEmptyLine(sc);if(line2null){return;}// 读取第三行targetStringline3readNonEmptyLine(sc);if(line3null){return;}String[]partsline1.split(\\s);int[]numsnewint[parts.length];for(inti0;iparts.length;i){nums[i]Integer.parseInt(parts[i]);}intkInteger.parseInt(line2);longtargetLong.parseLong(line3);Arrays.sort(nums);// 前缀和prefix[i] 表示 nums[0..i-1] 的和long[]prefixnewlong[nums.length1];for(inti0;inums.length;i){prefix[i1]prefix[i]nums[i];}longanskSumCount(nums,prefix,0,k,target);System.out.println(ans);}/** * 读取非空行避免输入中有空行时出错 */privatestaticStringreadNonEmptyLine(Scannersc){while(sc.hasNextLine()){Stringlinesc.nextLine().trim();if(!line.isEmpty()){returnline;}}returnnull;}/** * 统计从 start 开始选 k 个数和为 target 的“不重复元组个数” */privatestaticlongkSumCount(int[]nums,long[]prefix,intstart,intk,longtarget){intnnums.length;// 数量不够直接无解if(n-startk){return0;}// 最底层2Sum用双指针统计唯一配对个数if(k2){returntwoSumCount(nums,start,target);}longans0;// 枚举当前层的第一个数for(intistart;in-k;i){// 同一层去重相同值只保留第一次出现的位置if(istartnums[i]nums[i-1]){continue;}// 剪枝1选 nums[i] 后后面取最小的 k-1 个数若都大于 target则后面更不可能longminPossiblenums[i]rangeSum(prefix,i1,ik);if(minPossibletarget){break;}// 剪枝2选 nums[i] 后后面取最大的 k-1 个数若都小于 target则当前 nums[i] 太小longmaxPossiblenums[i]rangeSum(prefix,n-(k-1),n);if(maxPossibletarget){continue;}// 递归去下一层找 k-1 个数anskSumCount(nums,prefix,i1,k-1,target-nums[i]);}returnans;}/** * 统计有序数组中从 start 到末尾和为 target 的唯一二元组个数 * 例如[1,1,2,2] 中 target3只统计 (1,2) 这一个“值对” */privatestaticlongtwoSumCount(int[]nums,intstart,longtarget){intlstart;intrnums.length-1;longcount0;while(lr){longsum(long)nums[l]nums[r];if(sumtarget){count;// 记录当前左右值跳过重复值保证不重复计数intleftValnums[l];intrightValnums[r];while(lrnums[l]leftVal){l;}while(lrnums[r]rightVal){r--;}}elseif(sumtarget){l;}else{r--;}}returncount;}/** * 计算前缀和区间 [l, r) 的和 */privatestaticlongrangeSum(long[]prefix,intl,intr){returnprefix[r]-prefix[l];}}七、效果展示1、输入1 2 3 431002、输出03、说明不存在 3 个数的和等于 100。下一篇华为OD机试 - 简易内存池 - 逻辑分析Java 新系统 200分本专栏收录于《华为OD机试JAVA真题》。刷的越多抽中的概率越大私信哪吒备注华为OD加入华为OD刷题交流群每一题都有详细的答题思路、详细的代码注释、3个测试用例、为什么这道题采用XX算法、XX算法的适用场景发现新题目随时更新全天CSDN在线答疑。