算法分类——数组经典题目
数组是大多数程序语言中最基本的数据结构之一，也是用得最多的数据结构之一，因此对数组的操作和应用非常重要。在本文中，我们将会介绍一些数组的经典题目，它们在算法考试和编程面试中出现的概率非常高。
1. 两数之和
题目描述：
给定一个整数数组nums和一个目标值target，请在数组中找出和为目标值的两个整数。
你可以假设每个输入整数只会对应一个答案。
但是，你不能重复利用这个数组中同样的元素。
示例：
给定nums = [2, 7, 11, 15], target = 9 因为nums[0] + nums[1] = 2 + 7 = 9 所以返回[0, 1]
代码实现：
class Solution: def twoSum(self, nums: List[int], target: int) -> List[int]: hashmap = {} for i, num in enumerate(nums): if target - num in hashmap: return [hashmap[target - num], i] hashmap[num] = i
思路解析：
本题可以用哈希表的方式来解决。我们可以建立一个哈希表，用来存储每个数及其对应的下标，然后遍历数组，对于每个数，我们在哈希表中查询是否存在有相加等于target的数，如果存在，就可以返回答案。
时间复杂度：O(n)
空间复杂度：O(n)
2. 移动零
题目描述：
给定一个数组nums，编写一个函数将所有0移动到数组的末尾，同时保持非零元素的相对顺序。
示例:
输入: [0,1,0,3,12] 输出: [1,3,12,0,0]
代码实现：
class Solution: def moveZeroes(self, nums: List[int]) -> None: """ Do not return anything, modify nums in-place instead. """ i, j = 0, 0 while j < len(nums): if nums[j] != 0: nums[i], nums[j] = nums[j], nums[i] i += 1 j += 1
思路解析：
本题可以采用双指针的方式解决。假设有两个指针i和j，其中i指向当前已经处理好的序列的尾部，j则是当前遍历到的下标。每次将nums[j]与nums[i]交换，这样就能保证0都移到了数组的末尾。
时间复杂度：O(n)
空间复杂度：O(1)
3. 买卖股票的最佳时机
题目描述：
给定一个数组，它的第i个元素是一支给定股票第i天的价格。
如果你最多只允许完成一次交易（买一次和卖一次），设计一个算法来计算你所能获取的最大利润。
注意你不能在买入股票前卖出股票。
示例:
输入: [7,1,5,3,6,4] 输出: 5 解释: 在第2天（股票价格 = 1）的时候买入，在第5天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5。 注意利润不能是7-1 = 6, 因为卖出价格需要大于买入价格。
代码实现：
class Solution: def maxProfit(self, prices: List[int]) -> int: min_price, max_profit = float('inf'), 0 for price in prices: min_price = min(min_price, price) max_profit = max(max_profit, price - min_price) return max_profit
思路解析：
本题可以采用贪心算法的思路来解决。我们可以遍历整个数组，用min_price来记录历史最低价格，用max_profit来记录当前最大利润。
时间复杂度：O(n)
空间复杂度：O(1)
4. 旋转数组
题目描述：
给定一个数组，将数组中的元素向右移动k个位置，其中k是非负数。
示例1:
输入: [1,2,3,4,5,6,7] 和 k = 3 输出: [5,6,7,1,2,3,4] 解释: 向右旋转3步，即将数组[1,2,3,4,5,6,7]变为[7,6,5,4,3,2,1]，然后截取前三个元素[7,6,5]，再将剩下的元素[4,3,2,1]反转，最后将两个子数组拼接即可得到结果[5,6,7,1,2,3,4]。
示例2:
输入: [-1,-100,3,99] 和 k = 2 输出: [3,99,-1,-100] 解释: 向右旋转2步，即将数组[-1,-100,3,99]变为[99,3,-1,-100]，注意k可以大于数组长度，所以需要先对k做取模运算，如k=2时表示向右旋转2个位置，其实就是向右旋转2个位置之后又返回到了原来的位置，即k=2 % len(nums) = 2。
代码实现：
class Solution: def rotate(self, nums: List[int], k: int) -> None: """ Do not return anything, modify nums in-place instead. """ k %= len(nums) nums[:len(nums) - k] = reversed(nums[:len(nums) - k]) nums[len(nums) - k:] = reversed(nums[len(nums) - k:]) nums.reverse()
思路解析：
本题可以采用旋转数组的思路来解决。就是先将整个数组反转一遍，然后将前k个元素和后面的元素分别进行反转，最后得到旋转后的数组。
时间复杂度：O(n)
空间复杂度：O(1)
5. 存在重复元素
题目描述：
给定一个整数数组，判断是否存在重复元素。
如果存在一值在数组中出现至少两次，函数返回true。如果数组中每个元素都不相同，则返回false。
示例1:
输入: [1,2,3,1] 输出: true
示例2:
输入: [1,2,3,4] 输出: false
代码实现：
class Solution: def containsDuplicate(self, nums: List[int]) -> bool: return len(set(nums)) != len(nums)
思路解析：
本题可以先将数组进行去重，然后比较去重后的数组长度和原始数组长度是否一致来判断是否存在重复元素。
时间复杂度：O(n)
空间复杂度：O(n)
6. 只出现一次的数字
题目描述：
给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。
找出那个只出现了一次的元素。
示例:
输入: [2,2,1] 输出: 1
代码实现：
class Solution: def singleNumber(self, nums: List[int]) -> int: res = 0 for num in nums: res ^= num return res
思路解析：
本题可以采用异或运算的方式来解决。因为异或运算有一个很好的性质：任何数和自己本身异或都等于0，即a ^ a = 0，且异或运算
