用AI做算法题1

1、python 求解两个数组nums1 nums2的交集

在Python中，你可以使用多种方法来求解两个数组（nums1 和 nums2）的交集。下面是几种常见的方法：

方法1：使用集合（Set）

集合是一个无序且不重复的元素集，它非常适合用于求解交集这样的操作。

python
Copy Code

def intersection(nums1, nums2):
    # 将两个列表转换为集合
    set1 = set(nums1)
    set2 = set(nums2)
    
    # 使用集合的交集操作
    return list(set1 & set2)

# 示例
nums1 = [1, 2, 2, 1]
nums2 = [2, 2]
print(intersection(nums1, nums2))  # 输出: 

方法2：使用列表推导式和集合

如果你不想显式地创建集合，也可以使用列表推导式和集合来求解交集。

python
Copy Code

def intersection(nums1, nums2):
    # 使用列表推导式和集合来求解交集
    return list(set([num for num in nums1 if num in nums2]))

# 示例
nums1 = [1, 2, 2, 1]
nums2 = [2, 2]
print(intersection(nums1, nums2))  # 输出: 

方法3：使用collections.Counter

collections.Counter 可以用来计算每个元素出现的次数，然后你可以通过比较两个计数器来找出交集。

python
Copy Code

from collections import Counter

def intersection(nums1, nums2):
    # 计算两个列表的元素频率
    counter1 = Counter(nums1)
    counter2 = Counter(nums2)
    
    # 找出两个计数器的公共键，并取最小的频率值
    common = {key: min(counter1[key], counter2[key]) for key in counter1 if key in counter2}
    
    # 将字典转换回列表
    return [item for item, count in common.items() for _ in range(count)]

# 示例
nums1 = [1, 2, 2, 1]
nums2 = [2, 2]
print(intersection(nums1, nums2))  # 输出: [2, 2]

注意，这种方法会保留交集中元素的出现次数。如果你只想要唯一的交集元素，可以像前面两种方法那样使用集合来去重。

方法4：使用itertools（仅适用于小数据集）

对于非常小的数据集，你也可以使用itertools库中的filterfalse函数结合匿名函数来求解交集。但这种方法通常不如前面的方法高效。

python
Copy Code

from itertools import filterfalse

def intersection(nums1, nums2):
    # 使用filterfalse和匿名函数来求解交集
    return list(filterfalse(lambda x: x not in nums2, nums1))

# 注意：这种方法不会去除重复元素，所以结果可能包含重复项
# 示例
nums1 = [1, 2, 2, 1]
nums2 = [2, 2]
print(intersection(nums1, nums2))  # 输出: [2, 2, 1, 2] （这不是期望的结果）

# 要去重，可以结合set使用
print(list(set(intersection(nums1, nums2))))  # 输出: [1, 2]

通常，方法1和方法2是最常用且最高效的，因为它们直接利用了集合的交集操作，而且代码简洁易懂。如果你需要保留交集中元素的出现次数，可以选择方法3。

2、给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树

在Java中，判断一个二叉树是否是有效的二叉搜索树（BST, Binary Search Tree），我们通常需要采用递归或迭代的方式遍历树，并在遍历的过程中验证每个节点是否满足BST的定义。一个有效的BST，对于每个节点，其左子树的所有节点值都必须小于该节点的值，而右子树的所有节点值都必须大于该节点的值。

为了实现这一点，我们可以定义一个辅助方法，该方法通过递归遍历树，并利用一个范围（由最小值和最大值构成）来检查每个节点是否满足条件。对于根节点，这个范围可以是负无穷大到正无穷大。随着我们深入树中，这个范围会根据当前节点的值进行更新。

以下是一个使用递归的Java实现，用于判断给定的二叉树是否是有效的二叉搜索树：

java
Copy Code

public class Solution {
    public boolean isValidBST(TreeNode root) {
        return isValidBSTHelper(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }

    // 辅助方法，带有节点值范围的判断
    private boolean isValidBSTHelper(TreeNode node, long minVal, long maxVal) {
        // 空节点被视为有效的BST
        if (node == null) {
            return true;
        }

        // 如果节点的值不满足当前的范围，则不是BST
        if (node.val <= minVal || node.val >= maxVal) {
            return false;
        }

        // 递归检查左子树和右子树，注意要更新范围
        return isValidBSTHelper(node.left, minVal, node.val) &&
               isValidBSTHelper(node.right, node.val, maxVal);
    }

    // 树的节点定义
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }
}

在这个实现中，isValidBST方法是公开的接口，它调用了一个私有的辅助方法isValidBSTHelper。isValidBSTHelper方法接收当前节点以及该节点值的有效范围作为参数。如果当前节点为空，返回true（因为空树被视为有效的BST）。如果节点的值不在给定的范围内，返回false。否则，递归地检查左子树和右子树，同时更新范围：对于左子树，上界变为当前节点的值；对于右子树，下界变为当前节点的值。

请注意，这里使用了long类型来定义范围，以避免在节点值接近Integer.MAX_VALUE或Integer.MIN_VALUE时发生整数溢出。

class Solution {
    long pre = Long.MIN_VALUE;
    public boolean isValidBST(TreeNode root) {
        if (root == null) {
            return true;
        }
        // 访问左子树
        if (!isValidBST(root.left)) {
            return false;
        }
        // 访问当前节点：如果当前节点小于等于中序遍历的前一个节点，说明不满足BST，返回 false；否则继续遍历
        if (root.val <= pre) {
            return false;
        }
        pre = root.val;
        // 访问右子树
        return isValidBST(root.right);
    }
}

3、给你二叉树的根节点 root ，返回其节点值的 层序遍历 。

层序遍历（也称为广度优先搜索，BFS）是一种遍历二叉树的方法，它按照树的层级，从上到下、从左到右的顺序访问每个节点。在Java中，我们通常使用队列（Queue）来实现层序遍历，因为队列遵循先进先出的原则，这非常适合按层级处理节点。

下面是一个Java实现，用于返回二叉树节点值的层序遍历结果：

java
Copy Code
import java.util.*;

public class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        if (root == null) {
            return result;
        }

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root); // 将根节点加入队列

        while (!queue.isEmpty()) {
            int levelSize = queue.size(); // 当前层级的节点数
            List<Integer> currentLevel = new ArrayList<>();

            for (int i = 0; i < levelSize; i++) {
                TreeNode currentNode = queue.poll(); // 从队列中取出节点
                currentLevel.add(currentNode.val); // 将节点值添加到当前层级列表中

                // 将当前节点的子节点加入队列（如果存在）
                if (currentNode.left != null) {
                    queue.offer(currentNode.left);
                }
                if (currentNode.right != null) {
                    queue.offer(currentNode.right);
                }
            }

            result.add(currentLevel); // 将当前层级列表添加到结果中
        }

        return result;
    }

    // 树的节点定义
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }
}


在这个实现中，我们首先创建一个result列表，用于存储最终的层序遍历结果。然后，我们检查根节点是否为空，如果为空则直接返回空的结果列表。

接下来，我们创建一个队列queue，并将根节点加入队列。然后，我们进入一个循环，该循环将持续到队列为空为止。在每次循环中，我们首先获取当前层级的节点数（即队列的大小），然后创建一个currentLevel列表来存储当前层级的节点值。

接着，我们使用一个内部循环来处理当前层级的所有节点。在每个迭代中，我们从队列中取出一个节点，将其值添加到currentLevel列表中，并将该节点的子节点（如果存在）加入队列以供后续处理。

完成当前层级的处理后，我们将currentLevel列表添加到result列表中，然后继续处理下一层级，直到队列为空。

最后，我们返回result列表，它包含了二叉树节点值的层序遍历结果。

输入：root = [3,9,20,null,null,15,7]
输出：[[3],[9,20],[15,7]]
输入：root = [1]
输出：[[1]]

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        //返回的结果
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        if(null == root){
            return res;
        }
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        //根节点入队
        queue.add(root);
        while(!queue.isEmpty()){
            //一层的结果
            List<Integer> level = new ArrayList<Integer>();
            int levelCount = queue.size();
            //添加节点到一层的List中去
            for(int i = 0; i < levelCount ; i ++){
                //节点出队
                TreeNode node = queue.remove();
                //节点的左子树入队
                if(node.left != null){
                  queue.add(node.left);   
                }
                //节点的右子树入队   
                if(node.right != null){
                  queue.add(node.right);   
                }
                level.add(node.val);
            }
            res.add(level);
        }
        return res;
    }
}

4、给你一个整数数组 nums，找到峰值元素并返回其索引

示例 1：输入：nums = [1,2,3,1]
输出：2
解释：3 是峰值元素，你的函数应该返回其索引 2。
示例 2：输入：nums = [1,2,1,3,5,6,4]
输出：1 或 5
解释：你的函数可以返回索引 1，其峰值元素为 2；
或者返回索引 5， 其峰值元素为 6。
在Python中，我们可以通过遍历数组来查找峰值元素。由于题目要求只需要返回任何一个峰值的位置，我们可以采用一种简单的线性搜索策略。在遍历过程中，一旦我们发现当前元素的值大于其相邻元素（如果存在的话），就可以立即返回该元素的索引。
在Python中，我们可以通过遍历数组来查找峰值元素。由于题目要求只需要返回任何一个峰值的位置，我们可以采用一种简单的线性搜索策略。在遍历过程中，一旦我们发现当前元素的值大于其相邻元素（如果存在的话），就可以立即返回该元素的索引。

以下是一个实现这一策略的Python函数：

python
Copy Code

def findPeakElement(nums):
    # 边界情况处理：如果数组只有一个元素，那它本身就是峰值
    if len(nums) == 1:
        return 0
    
    # 遍历数组，查找峰值
    for i in range(len(nums)):
        # 检查当前元素是否是峰值
        # 注意边界条件：第一个元素没有左邻居，最后一个元素没有右邻居
        if (i == 0 or nums[i] > nums[i - 1]) and (i == len(nums) - 1 or nums[i] > nums[i + 1]):
            return i

# 示例用法
nums = [1, 2, 3, 1]
print(findPeakElement(nums))  # 输出: 2，因为nums是峰值元素3

在这个函数中，我们首先处理了一个边界情况：如果数组只有一个元素，那么该元素本身就是峰值，我们直接返回索引0。

接下来，我们使用一个for循环遍历数组。对于每个元素，我们检查它是否是峰值。根据峰值的定义，一个元素如果大于其左邻居和右邻居（如果存在的话），那么它就是峰值。因此，我们需要检查两个条件：

如果当前元素是第一个元素，或者它大于其左邻居。
如果当前元素是最后一个元素，或者它大于其右邻居。

如果这两个条件同时满足，那么我们就找到了一个峰值元素，并返回其索引。

注意，在遍历过程中，我们一旦找到峰值就会立即返回，因此这个函数的时间复杂度是O(n)，其中n是数组的长度。在最坏的情况下，我们可能需要检查数组中的每个元素才能找到峰值。

class Solution {
    public int findPeakElement(int[] nums) {
        int left = 0, right = nums.length - 1;
        for (; left < right; ) {
            int mid = left + (right - left) / 2;
            if (nums[mid] > nums[mid + 1]) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }
}

5、给你一个字符串 s，找到 s 中最长的 回文子串

示例 1：输入：s = “babad”
输出：“bab”
解释：“aba” 同样是符合题意的答案。
示例 2：输入：s = “cbbd”
输出：“bb”

在Python中，寻找最长回文子串是一个经典的问题，有多种解决方法。其中，动态规划（Dynamic Programming, DP）和中心扩展法（Expand Around Center）是两种常用的方法。这里，我将展示使用中心扩展法来实现这一功能的Python代码。

中心扩展法的核心思想是，对于字符串中的每一个字符（或者每一对相邻字符，考虑到回文串长度可能为奇数或偶数），我们尝试以该字符（或字符对）为中心，向两侧扩展，直到无法再扩展为止。在这个过程中，我们记录扩展得到的回文串的长度和起始位置，以便在遍历结束后找到最长的回文子串。

以下是使用中心扩展法寻找最长回文子串的Python实现：

python
Copy Code

def longestPalindrome(s: str) -> str:
    if not s or len(s) < 1:
        return ""
    
    start, end = 0, 0
    
    for i in range(len(s)):
        len1 = expandAroundCenter(s, i, i)       # 奇数长度的回文串
        len2 = expandAroundCenter(s, i, i + 1)   # 偶数长度的回文串
        max_len = max(len1, len2)
        
        # 如果当前找到的回文串比之前记录的更长，则更新起始和结束位置
        if max_len > end - start:
            start = i - (max_len - 1) // 2
            end = i + max_len // 2
    
    return s[start:end + 1]

def expandAroundCenter(s, left, right):
    while left >= 0 and right < len(s) and s[left] == s[right]:
        left -= 1
        right += 1
    # 返回回文串的长度（注意要减去1，因为我们在循环中多扩展了一步）
    return right - left - 1

# 示例用法
s = "babad"
print(longestPalindrome(s))  # 输出: "bab" 或者 "aba"（两者都是最长回文子串）

在这个实现中，longestPalindrome函数是主函数，它遍历字符串s中的每个字符，并尝试以该字符（或字符和它的下一个字符）为中心扩展回文串。expandAroundCenter函数负责实际的扩展过程，它接收一个字符串和两个索引作为参数，并返回以这两个索引为中心的回文串的长度。

在longestPalindrome函数中，我们使用start和end变量来记录最长回文子串的起始和结束位置。在每次扩展之后，我们都会检查当前回文串的长度是否比之前记录的最长回文串更长，如果是，则更新start和end的值。

最后，我们返回从start到end（包含end）的子串，即最长回文子串。

class Solution {
    public String longestPalindrome(String s) {
        char[] chars = s.toCharArray();

        int max = Integer.MIN_VALUE;
        int maxLeft = 0,maxRight = 1;
        for (int i = 0; i < chars.length; i++) {
            int left = kuoZhan(chars,i,i);
            int right = kuoZhan(chars,i,i + 1);
            int lenght = Math.max(left,right);
            max = Math.max(max,lenght);
            if (max == lenght) {
                maxLeft = i - (lenght - 1) / 2;
                maxRight = i + lenght / 2;
            }
        }
        return s.substring(maxLeft,maxRight + 1);
    }

    public int kuoZhan(char[] chars,int left,int right) {

        while (left >= 0 && right < chars.length && chars[left] == chars[right]) {
            left--;
            right++;
        }
        return right - left - 1;
    }
}

6、给你一个整数数组 nums 。如果任一值在数组中出现 至少两次 ，返回 true ，如果数组中每个元素互不相同，返回 false

示例 1：输入：nums = [1,2,3,1]
输出：true
解释：
元素 1 在下标 0 和 3 出现。
示例 2：输入：nums = [1,2,3,4]
输出：false
解释：
所有元素都不同。

在Python中，我们可以利用集合（set）的数据结构来高效地判断数组中是否存在重复元素。集合是一个无序且不重复的元素集，因此我们可以将数组转换为集合，并比较集合和数组的长度。如果它们的长度不同，说明数组中存在重复元素；如果长度相同，则数组中的元素都是唯一的。

以下是一个实现这一功能的Python函数：

python
Copy Code

def containsDuplicate(nums):
    # 将数组转换为集合，并比较长度
    return len(nums) != len(set(nums))

# 示例用法
nums = [1, 2, 3, 1]
print(containsDuplicate(nums))  # 输出: True，因为1出现了两次

nums = [1, 2, 3, 4]
print(containsDuplicate(nums))  # 输出: False，因为数组中的元素都是唯一的

在这个函数中，我们使用了set(nums)来将数组nums转换为一个集合。然后，我们使用len()函数来比较原始数组和集合的长度。如果它们的长度不同，说明数组中存在重复元素，函数返回True；否则，返回False。

这种方法的时间复杂度是O(n)，其中n是数组的长度，因为我们需要遍历整个数组来构建集合，并且集合的构建操作是线性的。空间复杂度也是O(n)，因为我们需要额外的空间来存储集合中的元素。
解题思路❝拿一个map存储元素出现的个数即可。

class Solution {
    public boolean containsDuplicate(int[] nums) {
        Map<Integer,Integer> map = new HashMap<>();
        for (int num : nums) {
            if (map.containsKey( num )) {
                return true;
            }else{
                map.put( num,0 );
            }
        }
        return false;
    }
}

7、给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。

示例 1:输入: nums = [1,2,3,4,5,6,7], k = 3
输出: [5,6,7,1,2,3,4]
解释:
向右轮转 1 步: [7,1,2,3,4,5,6]
向右轮转 2 步: [6,7,1,2,3,4,5]
向右轮转 3 步: [5,6,7,1,2,3,4]
示例 2:输入：nums = [-1,-100,3,99], k = 2
输出：[3,99,-1,-100]
解释:
向右轮转 1 步: [99,-1,-100,3]
向右轮转 2 步: [3,99,-1,-100]

在Python中，我们可以通过多种方式实现数组的右旋转。一个直观的方法是使用切片操作，这可以非常简洁地完成任务。另一种方法是使用额外的数组来模拟旋转过程，虽然这种方法可能不是最优的，但它有助于理解旋转的逻辑。

这里，我将展示使用切片操作来实现数组右旋转的Python代码：

python
Copy Code

def rotate(nums, k):
    # 确保k的值不超过数组的长度
    k = k % len(nums)
    # 使用切片操作实现右旋转
    nums[:] = nums[-k:] + nums[:-k]

# 示例用法
nums = [1, 2, 3, 4, 5, 6, 7]
k = 3
rotate(nums, k)
print(nums)  # 输出: [5, 6, 7, 1, 2, 3, 4]

在这个实现中，我们首先通过k = k % len(nums)确保k的值不会超过数组nums的长度。这是因为旋转数组的长度是周期性的，旋转len(nums)次后数组会回到原始状态。

接下来，我们使用切片操作nums[:] = nums[-k:] + nums[:-k]来实现右旋转。这里，nums[-k:]表示取数组nums的最后k个元素，nums[:-k]表示取数组nums的前len(nums)-k个元素。将这两个切片连接起来，就得到了右旋转k个位置后的新数组，并通过赋值操作nums[:]更新原数组。

注意，这里的切片赋值操作nums[:]是直接在原数组上进行修改，因此不需要返回任何值。函数执行后，原数组nums就会被更新为右旋转k个位置后的数组。

解题思路❝通过将每个数向右移动 k 个位置，我们能可以发现会将末尾k%n个数放置到头部，将头部剩余的数放到尾部。那么我们可以直接整个数组继续翻转，再将[0, k-1] 和 [k, n-1]索引位置翻转即可。
代码实现Java代码：

class Solution {
    public void rotate(int[] nums, int k) {
        k %= nums.length;
        reverse(nums, 0, nums.length - 1);
        reverse(nums, 0, k - 1);
        reverse(nums, k, nums.length - 1);
    }
    public void reverse(int[] nums, int l, int r) {
        for (int i = l, j = r; i < j; i++, j--) {
            int t = nums[i];
            nums[i] = nums[j];
            nums[j] = t;
        }
    }
}

8、给你一个整数数组 nums，返回 数组 answer ，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。请 不要使用除法，且在 O(n) 时间复杂度内完成此题。示例 1:输入: nums = [1,2,3,4]

输出: [24,12,8,6]
示例 2:输入: nums = [-1,1,0,-3,3]
输出: [0,0,9,0,0]
解题思路❝先让dp数组反向遍历nums取得nums中当前下标之后的所有值的积。然后正向遍历，使上一步得到的值与nums中当前下标之前的所有值相乘。代码实现Java代码：

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int [] dp = new int [nums.length];
        dp[nums.length-1] = 1;//使乘法生效
        for(int i = nums.length-2 ; i >= 0 ; i--){
            dp[i] = dp[i+1]*nums[i+1];
        }
        int dp1 = nums[0];
        for(int i = 1 ; i < nums.length ; i++){
            dp[i] = dp[i]*dp1;
            dp1 *= nums[i];
        }
        return dp;
    }
}

要在O(n)时间复杂度内完成这个任务，并且不使用除法，我们可以利用两个辅助数组来分别存储每个元素左侧所有元素的乘积和右侧所有元素的乘积。然后，我们可以通过遍历原始数组，将左侧乘积和右侧乘积相乘来得到答案。

但是，为了优化空间复杂度，我们可以只使用两个变量来代替两个辅助数组，分别记录当前元素左侧的乘积和右侧乘积的累积值。我们可以先计算出每个元素左侧的乘积，并将其存储在答案数组中。然后，我们从右向左遍历数组，同时累积右侧乘积，并将其与先前计算的左侧乘积相乘，从而得到最终结果。

以下是使用这种方法的Python实现：

python
Copy Code

def productExceptSelf(nums):
    n = len(nums)
    answer =  * n
    
    # 计算每个元素左侧的乘积
    left_product = 1
    for i in range(n):
        answer[i] = left_product
        left_product *= nums[i]
    
    # 计算每个元素右侧的乘积，并与左侧的乘积相乘
    right_product = 1
    for i in range(n-1, -1, -1):
        answer[i] *= right_product
        right_product *= nums[i]
    
    return answer

# 示例用法
nums1 = [1, 2, 3, 4]
print(productExceptSelf(nums1))  # 输出: [24, 12, 8, 6]

nums2 = [-1, 1, 0, -3, 3]
print(productExceptSelf(nums2))  # 输出: [0, 0, 9, 0, 0]

在这个实现中，我们首先初始化一个与原始数组nums长度相同的答案数组answer，并将其所有元素设置为1。然后，我们使用left_product变量来累积当前元素左侧的乘积，并将其存储在答案数组的相应位置。接下来，我们使用right_product变量从右向左累积乘积，并将其与答案数组中已有的左侧乘积相乘，从而得到最终结果。

这种方法的时间复杂度是O(n)，因为我们只遍历了数组两次。空间复杂度是O(1)（除了答案数组本身），因为我们只使用了两个额外的变量来存储左侧和右侧的乘积。

9、给定一个二进制数组 nums ，找到含有相同数量的 0 和 1 的最长连续子数组，并返回该子数组的长度。

示例 1:输入: nums = [0,1]
输出: 2
说明: [0, 1] 是具有相同数量 0 和 1 的最长连续子数组。
示例 2:输入: nums = [0,1,0]
输出: 2
说明: [0, 1] (或 [1, 0]) 是具有相同数量0和1的最长连续子数组。

为了找到含有相同数量的0和1的最长连续子数组，我们可以利用哈希表（字典）来记录从数组起始位置到当前位置的0和1的数量之差，并更新最大连续子数组的长度。

具体思路是，当我们遍历数组时，我们可以维护一个计数器count，它表示到目前为止0和1的数量之差（0的个数减去1的个数）。每当我们遇到一个0，count就减1；每当我们遇到一个1，count就加1。我们将count的值作为哈希表的键，而哈希表的值则是当前count第一次出现时的索引位置。

如果在遍历过程中我们发现count的值已经在哈希表中存在，那么说明从哈希表中记录的索引位置到当前位置的子数组中0和1的数量是相等的（因为count的值为0表示0和1的数量相等，或者它们在某个位置之前的数量差与当前位置相同，从而相互抵消）。此时，我们可以计算这个子数组的长度，并更新最大长度。

以下是使用这种方法的Python实现：

python
Copy Code

def findMaxLength(nums):
    count = 0
    max_length = 0
    index_map = {0: -1}  # 初始化哈希表，count为0时索引为-1
    
    for i, num in enumerate(nums):
        # 更新count值
        if num == 0:
            count -= 1
        else:
            count += 1
        
        # 如果count已经在哈希表中，计算子数组长度并更新最大长度
        if count in index_map:
            max_length = max(max_length, i - index_map[count])
        else:
            # 如果count不在哈希表中，记录其第一次出现的索引
            index_map[count] = i
    
    return max_length

# 示例用法
nums1 = [0, 1]
print(findMaxLength(nums1))  # 输出: 2

nums2 = [0, 1, 0]
print(findMaxLength(nums2))  # 输出: 2

在这个实现中，我们使用了一个哈希表index_map来记录每个count值第一次出现的索引位置。我们初始化count为0，并设置index_map = -1，表示在数组开始之前，0和1的数量相等（即差值为0）的索引位置是-1。然后，我们遍历数组，更新count值，并根据count值来更新最大连续子数组的长度。最后，我们返回最大长度作为结果。
解题思路❝利用前缀和 sum ，遇到 0 时减一，遇到 1 时加一，把前缀和 sum 和下标 i 存入哈希表中。如果当前 sum 在哈希表中存在，则说明 当前下标 i 到 sum 第一次出现的下标（在哈希表中对应的value）。这个范围内，0 和 1 出现次数相同，因为这个范围内的前缀和为 0 ，迭代最大长度 len，最后返回 len。代码实现Java代码：

class Solution {
    public int findMaxLength(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();
        int sum = 0;
        int len = 0;
        map.put(0, -1);
        for(int i = 0; i < nums.length; i++) {
            if(nums[i] == 1) sum += 1;
            else sum -= 1;
            if(map.containsKey(sum)){
                len = Math.max(len, i - map.get(sum));
            }
            else {
                map.put(sum, i);
            }
        }
        return len;
    }
}

10、给定两个字符串 s 和 t ，判断它们是否是同构的。如果 s 中的字符可以按某种映射关系替换得到 t ，那么这两个字符串是同构的。每个出现的字符都应当映射到另一个字符，同时不改变字符的顺序。不同字符不能映射到同一个字符上，相同字符只能映射到同一个字符上，字符可以映射到自己本身。

示例 1:输入：s = “egg”, t = “add”
输出：true
示例 2：输入：s = “foo”, t = “bar”
输出：false

要判断两个字符串s和t是否是同构的，我们可以使用两个字典来建立字符之间的映射关系。一个字典用于记录s中字符到t中字符的映射，另一个字典用于记录t中字符到s中字符的映射。这样，我们可以确保映射是双向的，并且每个字符都有唯一的映射。

在遍历s和t的过程中，我们检查当前字符的映射是否存在。如果存在，我们验证映射是否一致；如果不存在，我们建立新的映射。如果发现映射不一致或字符已经存在不同的映射，则返回False。如果遍历完成后没有发现任何问题，则返回True。

以下是使用这种方法的Python实现：

python
Copy Code

def isIsomorphic(s: str, t: str) -> bool:
    if len(s) != len(t):
        return False
    
    s_to_t = {}
    t_to_s = {}
    
    for char_s, char_t in zip(s, t):
        # 检查s到t的映射
        if char_s in s_to_t:
            if s_to_t[char_s] != char_t:
                return False
        else:
            s_to_t[char_s] = char_t
        
        # 检查t到s的映射
        if char_t in t_to_s:
            if t_to_s[char_t] != char_s:
                return False
        else:
            t_to_s[char_t] = char_s
    
    return True

# 示例用法
s1, t1 = "egg", "add"
print(isIsomorphic(s1, t1))  # 输出: True

s2, t2 = "foo", "bar"
print(isIsomorphic(s2, t2))  # 输出: False

在这个实现中，我们首先检查s和t的长度是否相等。如果不相等，它们一定不是同构的，因为同构字符串要求字符一一对应。然后，我们初始化两个字典s_to_t和t_to_s来记录字符之间的映射关系。接下来，我们使用zip函数同时遍历s和t中的字符，并检查映射关系是否一致或需要建立新的映射。如果发现任何不一致的映射或已经存在的不同映射，我们立即返回False。最后，如果遍历完成没有发现任何问题，我们返回True表示s和t是同构的。

代码实现Java代码：

class Solution {
 public boolean isIsomorphic(String s, String t) {
  char[] cs1 = s.toCharArray();
  char[] cs2 = t.toCharArray();
  char[] map1 = new char[256];
  char[] map2 = new char[256];
  int len = s.length();
  for (int i = 0; i < len; i++) {
   char c1 = cs1[i], c2 = cs2[i];
   if ((map1[c1] != 0 && map1[c1] != c2) || (map2[c2] != 0 && map2[c2] != c1)) {
    return false;
   }
   map1[c1] = c2;
   map2[c2] = c1;
  }
  return true;
 }

}