2023年华为OD机考真题：最多等和不相交连续子序列

算法刷题1年前 (2023)更新江南白衣

全网最全面的华为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