数组经典问题：两数之和与滑动窗口
数组是编程中最基本的数据结构之一，它以连续的内存空间存储一系列元素，支持快速的随机访问。在处理数组时，我们经常会遇到一些经典问题，其中“两数之和”和“滑动窗口”是两个非常典型的例子。本文将围绕这两个问题，探讨其解决方案和背后的算法思想。
一、两数之和
1. 问题描述
给定一个整数数组 `nums` 和一个目标值 `target`，请你在该数组中找出和为目标值的那两个整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。你不能重复利用这个数组中同样的元素。
2. 算法思路
2.1 暴力法
最简单的方法是遍历数组，对于每个元素 `nums[i]`，我们再遍历一次数组寻找 `target - nums[i]`。这种方法的时间复杂度为 O(n^2)，空间复杂度为 O(1)。
python
def twoSum(nums, target):
for i in range(len(nums)):
for j in range(i + 1, len(nums)):
if nums[i] + nums[j] == target:
return [i, j]
2.2 哈希表法
为了提高效率，我们可以使用哈希表来存储已经遍历过的元素及其索引。当遍历到某个元素 `nums[i]` 时，我们只需要检查 `target - nums[i]` 是否在哈希表中。如果在，则找到了答案；如果不在，则将 `nums[i]` 和其索引存入哈希表。这种方法的时间复杂度为 O(n)，空间复杂度为 O(n)。
python
def twoSum(nums, target):
hash_map = {}
for i, num in enumerate(nums):
complement = target - num
if complement in hash_map:
return [hash_map[complement], i]
hash_map[num] = i
二、滑动窗口
1. 问题描述
给定一个整数数组 `nums` 和一个滑动窗口的大小 `k`，请找出所有滑动窗口中的最大值。
2. 算法思路
2.1 暴力法
最简单的方法是遍历每个窗口，计算窗口内所有元素的最大值。这种方法的时间复杂度为 O(nk)，空间复杂度为 O(1)。
python
def maxSlidingWindow(nums, k):
result = []
for i in range(len(nums) - k + 1):
max_val = max(nums[i:i+k])
result.append(max_val)
return result
2.2 双端队列法
为了提高效率，我们可以使用双端队列（deque）来存储窗口内的最大值。双端队列的特点是，队首元素始终是窗口内的最大值。当窗口滑动时，我们只需要从队首移除窗口外的元素，并在队尾添加新元素。这种方法的时间复杂度为 O(n)，空间复杂度为 O(k)。
python
from collections import deque
def maxSlidingWindow(nums, k):
result = []
dq = deque()
for i, num in enumerate(nums):
移除窗口外的元素
if dq and dq[0] == i - k:
dq.popleft()
移除小于当前元素的元素
while dq and nums[dq[-1]] < num:
dq.pop()
添加当前元素
dq.append(i)
当窗口大小为 k 时，添加最大值到结果中
if i >= k - 1:
result.append(nums[dq[0]])
return result
三、总结
本文介绍了数组中的两个经典问题：“两数之和”和“滑动窗口”。通过分析问题，我们提出了不同的算法思路，并给出了相应的代码实现。在实际应用中，我们可以根据问题的规模和需求，选择合适的算法来提高程序的效率。
在解决这类问题时，我们不仅要关注算法的效率，还要注重代码的可读性和可维护性。通过不断练习和总结，我们可以提高自己的编程能力，为未来的项目打下坚实的基础。
Comments NOTHING