【力扣每日一题】力扣2765最长交替子数组

题目来源

力扣2765最长交替子数组

题目概述

给你一个下标从 0 开始的整数数组 nums 。如果 nums 中长度为 m 的子数组 s 满足以下条件，我们称它是一个 交替子数组 ：

m?大于?1?。?s1?=?s0?+?1?。 下标从?0?开始的子数组?s?与数组 [s0,?s1,?s0,?s1,...,s(m-1) % 2] 一样。也就是说，s1 - s0 = 1?，s2 - s1 = -1?，s3 - s2 = 1?，s4 - s3 = -1?，以此类推，直到 **s[m - 1] - s[m - 2] = (-1)m **。 请你返回?nums?中所有?交替?子数组中，最长的长度，如果不存在交替子数组，请你返回?-1?。

子数组是一个数组中一段连续?非空?的元素序列。

解题思路

思路一：记录交替数组首字符，当遇到可能是交替元素时将较小元素与首元素比较。 思路二： 记录上次两元素之差，遇到可能是交替元素时比较两次的差是不是相反数。

代码实现

java实现

java实现使用思路二

public class Solution {
    public int alternatingSubarray(int[] nums) {
        int lastSub = nums[1] - nums[0];
        int count = lastSub == 1 ? 2 : 0;
        int max = 0;
        for (int i = 2; i < nums.length; i++) {
            int currentSub = nums[i] - nums[i - 1];
            // 如果两元素差为1
            if (currentSub == 1 || currentSub == -1) {
                // 当为相反数时加入数组
                if (lastSub == -currentSub && count > 0) {
                    count++;
                // 数组起始
                }else if (currentSub == 1) {
                    max = Math.max(max, count);
                    count = 2;
                // 数组结束
                }else {
                    max = Math.max(max, count);
                    count = 0;
                }
            // 数组结束
            }else {
                max = Math.max(max, count);
                count = 0;
            }
            lastSub = currentSub;
        }
        max = Math.max(max, count);
        return max == 0 ? -1 : max;
    }
}

c++实现

c++使用思路一实现

class Solution {
public:
    int alternatingSubarray(vector<int>& nums) {
        int count = 0;
        int max = 0;
        int start = 0;
        for (int i = 1; i < nums.size(); i++) {
            // 如果前一个比后一个大
            if (nums[i] == nums[i - 1] - 1) {
                // 如果符合
                if (start == nums[i]) {
                    count++;
                }
                else if (count != 0) {
                    max = max > count ? max : count;
                    count = 0;
                    start = 0;
                }
                // 前一个比后一个小
            }
            else if (nums[i] == nums[i - 1] + 1) {
                // 还没有交替数组，开始计算交替数组
                if (start == 0) {
                    start = nums[i - 1];
                    count = 2;
                    // 已经有交替数组了，如果找到的数据符合交替数组，增加长度
                }
                else if (start == nums[i - 1]) {
                    count++;
                    // 已经开始计算交替数组了，并且找到的数据不符合，开启了一个新的数组
                }
                else {
                    max = max > count ? max : count;
                    start = nums[i - 1];
                    count = 2;
                }

            }
            else if (count != 0) {
                max = max > count ? max : count;
                count = 0;
                start = 0;
            }
        }
        max = max > count ? max : count;
        return max == 0 ? -1 : max;
    }
};