全网最全面的华为OD机试真题汇总，100%原题题库，不需要开会员即可查看全部内容，更多考题请查看真题库。
真题库：https://www.yuque.com/codernav.com/od
题目：最多等和不相交连续子序列
知识点贪心
时间限制：1s 空间限制：256MB 限定语言：不限
题目描述：
给定一个数组，我们称其中连续的元素为连续子序列，称这些元素的和为连续子序列的和。数组中可能存在几组连续子序列，组内的连续子序列互不相交且有相同的和。求一组连续子序列，组内子序列的数目最多。输出这个数目。
输入描述：
第一行输入为数组长度 N，1 <= N <= 10^3。
第二行为 N 个用空格分开的整数 Ci，-10^5 <= Ci <= 10^5。
输出描述：
第一行是一个整数 M，表示满足要求的最多的组内子序列的数目。
示例1
输入：
10
8 8 9 1 9 6 3 9 1 0
输出：
4
说明：
四个子序列的第一个元素和最后一个元素的下标分别为：
2 2
4 4
5 6
7 7
示例2
输入：
10
-1 0 4 -3 6 5 -6 5 -7 -3
输出：
3
说明：
三个子序列的第一个元素和最后一个元素的下标分别为：
3 3
5 8
9 9
解题思路：
使用map来放置子序列和和其首位坐标集合
Key：连续子序列和
Value：子序列的首位坐标集合
因为坐标集合中会存在相交的集合所以还必须进行处理
如例2：
子序列和为-3的坐标集合为[3，3]，[3，9]，[5，8][9，9]
[3，9]与[3，3]，[5，8]，[9，9]都存在交集。
[3，3]，[5，8]，[9，9]不存在交集，最长子序列数目为3。
代码实现一：
package com.codernav.demo.hwod.exam;
import java.util.*;
/**
* @title 最多等和不相交连续子序列
* @Description 某给定一个数组，我们称其中连续的元素为连续子序列，称这些元素的和为连续子序列的和。
* 数组中可能存在几组连续子序列，组内的连续子序列互不相交且有相同的和。求一组连续子序列，组内子序列的数目最多。输出这个数目；
* @Author 开发者导航
* @website https://codernav.com
* @date 2023/5/15
*/
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
sc.nextLine();
String[] strings = sc.nextLine().split(" ");
int[] ints = new int[N];
for (int i = 0; i < N; i++) {
ints[i] = Integer.parseInt(strings[i]);
}
Map<Integer, List<int[]>> map = new HashMap<>();
for (int i = 0; i < N; i++) {
int count = ints[i];
for (int j = i; j < N; j++) {
int[] temp = {i, j}; //首坐标i，尾座标j
if (i != j) { //单独的序列不需要进行求和
count += ints[j];
}
if (map.containsKey(count)) {
map.get(count).add(temp);
} else {
List<int[]> tempList = new ArrayList<>();
tempList.add(temp);
map.put(count, tempList);
}
}
}
int res = 0;
for (List<int[]> list : map.values()) {
int count = removeIntersect(list);
res = Math.max(res, count);
}
System.out.println(res);
}
/**
* 求出子序列中互不相交的最长子序列
*
* @param list 和相同的子序列集合
* @return 最长子序列的长度
*/
public static int removeIntersect(List<int[]> list) {
int count = 1;
int size = list.size();
int lastR = list.get(0)[1];
for (int i = 1; i < size; i++) {
if (lastR < list.get(i)[0]) {
//区域不相交，更新右边界
lastR = list.get(i)[1];
count++;
} else {
//区域相交
lastR = Math.min(lastR, list.get(i)[1]);
}
}
return count;
}
}
代码实现二：满分题解
package com.codernav.demo.hwod.exam;
import java.util.*;
/**
* @title 最多等和不相交连续子序列
* @Description 某给定一个数组，我们称其中连续的元素为连续子序列，称这些元素的和为连续子序列的和。
* 数组中可能存在几组连续子序列，组内的连续子序列互不相交且有相同的和。求一组连续子序列，组内子序列的数目最多。输出这个数目；
* @Author 开发者导航
* @website https://codernav.com
* @date 2023/5/15
*/
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = Integer.parseInt(sc.nextLine());
String[] strings = sc.nextLine().split(" ");
int[] nums = Arrays.stream(strings).mapToInt(Integer::parseInt).toArray();
//各元素到索引为0的和
int[] count = new int[N + 1];
int res = 1;
Map<Integer, Integer> cnt = new HashMap<>();
Map<Integer, Integer> last = new HashMap<>();
for (int i = 0; i < N; i++) {
//0 -> i+1 连续子序列之和
count[i + 1] = count[i] + nums[i];
for (int j = i; j >= 0; j--) {
//j -> i+1 连续子序列和
int target = count[i + 1] - count[j];
if (last.getOrDefault(target, 0) <= j) {
last.put(target, i + 1);
cnt.put(target, cnt.getOrDefault(target, 0) + 1);
res = Math.max(res, cnt.get(target));
}
}
}
System.out.println(res);
}
}
满分答案题解：例：nums = [-1,0,4,-3,6]
新建一个n+1长度的数组，来记录各位置到0的连续子序列的和
count = [0,0,0,0,0,0]（设置n+1为了方便计算）
0 0 0 0 0 0
遍历nums
1、当 i=0，count = [0,-1,0,0,0,0,0]；我们把第一个位置（索引0空出来以便后面计算）
i=0，说明只有一个子序列【-1】；
last = {-1:1} 说明和为 -1 的连续子序列到位置 1；
cnt = {- 1:1} 说明和为 -1 的连续子序列有 1 个
2、当 i=1，count = [0,-1,-1,0,0,0,0]；
i=1，说明有两个连续子序列【0】、【-1,0】；
想要求出所有连续子序列的和是多少，只需要从 i=1 往前遍历求 count 的差值即可；
a、【0】的和为：count[2] – count[1] = -1 – -1 = 0（这里大家应该能理解吧，后续都是用这种方式求得连续子串的和）
last = {-1:1; 0:2} 说明和为 0 的连续子序列到位置 2；
cnt = {-1:1; 0:1} 说明和为 0 的连续数组有 1 个；
b、【-1,0】的和为 count[2] – count[0] = -1 – 0 = -1；
说明连续子串 【-1,0】和为 -1，且需要往前计算到 0（count数组中的索引）的位置；而 last 中 -1 的值为 1，1>0，说明【-1，0】与之前和为 -1（【-1】）的连续子序列出现了交集，所以不记录这次的结果
3、当 i=2，count[3] = count[2] + nums[2] = -1 + 4 = 3，count = [0,-1,-1,3,0,0,0]；
i=2，说明有三个连续子序列【4】、【0,4】、【-1,0,4】;
a、【4】的和为：count[3] – count[2] = 3 – -1 = 4；
last={-1:1; 0:2; 4:3} 说明和为 4 的连续子序列到位置 3；
cnt = {-1:1; 0:1; 4:1} 说明和为 4 的连续数组有 1 个；
b、【0,4】的和为 count[3] – count[1] = 3 – -1 = 4；
而 last 中 4 的值为 3，3>1，说明【0,4】与之前和为4（【4】）的连续子序列出现了交集，所以不记录这次的结果；
c、【-1,0,4】的和为：count[3] – count[0] = 3 – 0 = 3；
last={-1:1; 0:2; 4:3; 3:3}说明和为3的连续子序列到位置3；
cnt = {-1:1; 0:1; 4:1; 3,1}说明和为 4 的连续数组有1个；
以此类推。。。
最后【-1,0,4】、【-3,6】都是3，所以结果为2
相关文章
