A.每日一题——3719. 最长平衡子数组 I

题目链接：3719. 最长平衡子数组 I（中等）

算法原理：

解法：暴力枚举

433ms击败28.06%

时间复杂度O(N²)

我的思考过程：

①看到“子数组是数组中连续且非空的一段元素序列”的条件反射第一反应是用滑动窗口来解，很像里面求子数组的模型👇

一轮复习——C.滑动窗口模型总结

但是仔细观察会发现，这题的条件并不涉及越长越好或者越少越好，也不涉及恰好型滑动窗口的“至多”或者“至少”，仅仅是单纯判断子区间内不同奇偶数数量是否相等，因此摒弃这个想法

②再观察数据量，发现1<=nums.length<=1500，这个数据量非常小了，因此考虑用暴力枚举的解法👇

固定每个 i 开头，在此后用 j 遍历每个子数组，并使用哈希表判断当前子数组中不同奇偶数数量是否相同，相同的话就更新最长符合的长度，最后返回即可

Java代码：

class Solution { public int longestBalanced(int[] nums) { int len=0; for(int i=0;i<nums.length;i++){ //判断以i开头的子数组是否符合条件 HashMap<Integer,Integer> even=new HashMap<>();//计数偶数 HashMap<Integer,Integer> odd=new HashMap<>();//计数奇数 for(int j=i;j<nums.length;j++){ HashMap<Integer,Integer> hash=(nums[j]%2==0)?even:odd; hash.put(nums[j],hash.getOrDefault(nums[j],0)+1); if(even.size()==odd.size()) len=Math.max(len,j-i+1); } } return len; } }