华为OD机试 - 最长连续子序列 - 双指针（Java 2023 B卷 100分）

华为OD机试 - 最长连续子序列 - 双指针（Java 2023 B卷 100分）-LMLPHP

专栏导读

本专栏收录于《华为OD机试（JAVA）真题（A卷+B卷）》。

刷的越多，抽中的概率越大，每一题都有详细的答题思路、详细的代码注释、样例测试，发现新题目，随时更新，全天CSDN在线答疑。

一、题目描述

有N个正整数组成的一个序列。给定整数sum，求长度最长的连续子序列，使他们的和等于sum，返回此子序列的长度，

如果没有满足要求的序列，返回-1。

二、输入描述

第一行输入是：N个正整数组成的一个序列

第二行输入是：给定整数sum

三、输出描述

最长的连续子序列的长度

备注

输入序列仅由数字和英文逗号构成，数字之间采用英文逗号分隔
序列长度：1 <= N <= 200
输入序列不考虑异常情况

四、双指针

1、双指针是什么？

双指针算法是一种非常有效的算法策略，常用于解决一些具有线性结构的问题，例如链表和数组。在Java中，我们可以通过使用两个指针（通常命名为 p1 和 p2）来遍历和操作数据结构。

以下是一个使用双指针算法来找到给定数组中是否存在重复元素的简单Java示例：

public class Main {  
    public static void main(String[] args) {  
        int[] arr = {1, 2, 3, 4, 5, 2};  
        System.out.println(containsDuplicate(arr));  
    }  
  
    public static boolean containsDuplicate(int[] nums) {  
        if (nums == null || nums.length < 2) {  
            return false;  
        }  
          
        for (int i = 0; i < nums.length; i++) {  
            for (int j = i + 1; j < nums.length; j++) {  
                if (nums[i] == nums[j]) {  
                    return true;  
                }  
            }  
        }  
        return false;  
    }  
}

在上述代码中，containsDuplicate 函数使用了两个嵌套的循环。外层循环遍历数组的每个元素，内层循环则从当前元素的下一个位置开始遍历数组。如果找到两个相等的元素，函数就返回 true。如果没有找到，就返回 false。

虽然这种方法可以解决问题，但是它的时间复杂度是 O(n^2)，在处理大规模数据时可能效率较低。为了提高效率，我们可以使用一个哈希集合来存储已经遍历过的元素，这样我们就可以在 O(n) 的时间复杂度内解决问题。

2、Java双指针算法适合解决哪些问题？

Java双指针算法适用于解决具有线性结构的问题，特别是需要在两个指针所指向的元素之间进行比较和操作的问题。以下是一些可以使用Java双指针算法解决的问题类型：

数组中是否存在重复元素：使用双指针分别从数组的两端开始，如果两个指针所指向的元素相等，则说明存在重复元素。
数组中的子数组和：使用双指针分别从数组的两端开始，通过计算两个指针所指向的元素之和，判断是否等于目标值，从而找到所有和为目标值的子数组。
排序数组中是否存在重复元素：使用双指针分别从排序数组的两端开始，如果两个指针所指向的元素相等且第二个指针仍然在范围内，则说明存在重复元素。
判断链表中是否存在环：使用双指针分别从链表的两端开始，如果两个指针在某一点相遇，则说明链表中存在环。
链表排序：使用双指针分别从链表的头部和尾部开始，通过比较节点值的大小决定如何移动指针，最终得到有序的链表。

这些只是Java双指针算法的一些应用示例，实际上，只要问题涉及到线性结构且需要在两个元素之间进行比较和操作，双指针算法都可以提供有效的解决方案。

五、解题思路

第一行输入若干个数字，逗号隔开；
第二个输入给定整数sum；
定义最长的连续子序列长度maxLen，默认-1；
通过双指针算法找到最长的连续子序列，使他们的和等于sum；
输出最长的连续子序列长度maxLen。

六、Java算法源码

package com.guor.od;

import java.util.*;

public class OdTest {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        // N个正整数组成的一个序列
        String input = sc.nextLine();
        // 给定整数sum
        int sum = Integer.parseInt(sc.nextLine());
        List<Integer> list = new ArrayList<>();
        Arrays.stream(input.split(",")).forEach(s -> {
            list.add(Integer.parseInt(s));
        });

        // 双指针算法
        int left = 0;
        int right = 0;
        // 临时的区间和
        int tempSum = list.get(left);

        /**
         * 最长的连续子序列长度
         * 如果没有满足要求的序列，返回-1
         */
        int maxLen = -1;
        while (right < list.size()) {
            if (tempSum < sum) {
                right++;
                if (right == list.size()){
                    break;
                }
                tempSum += list.get(right);
            } else if (tempSum > sum) {
                tempSum -= list.get(left);
                left++;
            } else {
                // 给定整数sum，求长度最长的连续子序列，使他们的和等于sum
                if (maxLen < right - left) {
                    // 返回此子序列的长度
                    maxLen = right - left + 1;
                }
                tempSum -= list.get(left);
                left++;
            }
        }
        System.out.println(maxLen);
    }
}

七、效果展示

1、输入

1,3,5,7,2
9

2、输出

3、说明

1,3,5和7,2两个序列均能满足要求，所以最长的连续序列为1,3,5，因此结果为3。

华为OD机试 - 最长连续子序列 - 双指针（Java 2023 B卷 100分）-LMLPHP

🏆下一篇：华为OD机试真题 Java 实现【简易内存池】【2023 B卷 200分考生抽中题】

🏆本文收录于，华为OD机试（JAVA）真题（A卷+B卷）

刷的越多，抽中的概率越大，每一题都有详细的答题思路、详细的代码注释、样例测试，发现新题目，随时更新，全天CSDN在线答疑。

哪吒