LeetCode数组题解：5大经典Python实战

以下是针对LeetCode热门题目Top 100 Liked Questions中“普通数组”类题目的Python版本解法指南。普通数组题目通常涉及数组的基本操作，如遍历、排序、查找等。我将逐步介绍几个代表性题目，提供Python代码和简要解释，帮助您理解和实现。

1. Two Sum（两数之和）

题目描述：给定一个整数数组nums和一个目标值target，在数组中找出和为目标值的两个整数，并返回它们的下标。假设只有一个有效解，且不能使用同一个元素两次。

Python解法：

def twoSum(nums, target): num_map = {} for i, num in enumerate(nums): complement = target - num if complement in num_map: return [num_map[complement], i] num_map[num] = i return []

代码解释：

• 使用哈希表num_map存储每个元素的值和下标。
• 遍历数组，计算当前元素的补数（target - num）。
• 如果补数在哈希表中，直接返回下标对。
• 时间复杂度：$O(n)$，空间复杂度：$O(n)$。

2. Maximum Subarray（最大子数组和）

题目描述：给定一个整数数组nums，找出连续子数组的最大和。

Python解法：

def maxSubArray(nums): max_sum = float('-inf') current_sum = 0 for num in nums: current_sum = max(num, current_sum + num) max_sum = max(max_sum, current_sum) return max_sum

代码解释：

• 初始化max_sum为负无穷和current_sum为0。
• 遍历数组，更新current_sum为当前元素或当前元素加上之前的子数组和的最大值。
• 同时更新max_sum为当前最大值。
• 时间复杂度：$O(n)$，空间复杂度：$O(1)$。

3. Move Zeroes（移动零）

题目描述：给定一个数组nums，将所有0移动到数组末尾，同时保持非零元素的相对顺序。

Python解法：

def moveZeroes(nums): non_zero_idx = 0 for i in range(len(nums)): if nums[i] != 0: nums[non_zero_idx], nums[i] = nums[i], nums[non_zero_idx] non_zero_idx += 1

代码解释：

• 使用双指针：non_zero_idx指向非零元素应放置的位置。
• 遍历数组，当遇到非零元素时，将其与non_zero_idx位置的元素交换，并移动指针。
• 时间复杂度：$O(n)$，空间复杂度：$O(1)$。

4. Container With Most Water（盛最多水的容器）

题目描述：给定一个整数数组height，表示垂直线的高度，找出两条线与x轴形成的容器能容纳的最大水量。

Python解法：

def maxArea(height): left, right = 0, len(height) - 1 max_area = 0 while left < right: width = right - left h = min(height[left], height[right]) max_area = max(max_area, width * h) if height[left] < height[right]: left += 1 else: right -= 1 return max_area

代码解释：

• 使用双指针从数组两端向中间移动。
• 计算当前指针位置形成的容器面积（宽度乘以最小高度）。
• 更新最大面积，并根据高度移动指针。
• 时间复杂度：$O(n)$，空间复杂度：$O(1)$。

5. Product of Array Except Self（除自身以外数组的乘积）

题目描述：给定一个数组nums，返回一个数组，其中每个元素是除自身外所有元素的乘积。要求不使用除法，并在$O(n)$时间内完成。

Python解法：

def productExceptSelf(nums): n = len(nums) left_products = [1] * n right_products = [1] * n answer = [1] * n # 计算左侧乘积 for i in range(1, n): left_products[i] = left_products[i-1] * nums[i-1] # 计算右侧乘积 for i in range(n-2, -1, -1): right_products[i] = right_products[i+1] * nums[i+1] # 合并结果 for i in range(n): answer[i] = left_products[i] * right_products[i] return answer

代码解释：

• 使用三个数组：left_products存储每个元素左侧的累积乘积，right_products存储右侧累积乘积。
• 先从左向右计算左侧乘积，再从右向左计算右侧乘积。
• 最后合并结果得到每个位置的乘积。
• 时间复杂度：$O(n)$，空间复杂度：$O(n)$。

这些题目覆盖了普通数组操作的核心技巧，如双指针、动态规划等。建议您在LeetCode平台上实际练习这些题目，加深理解。如果您有其他具体题目需求，我可以进一步提供帮助！