面试中的算法问题，有很多并不需要复杂的数据结构支撑。就是用数组，就能考察出很多东西了。其实，经典的排序问题，二分搜索等等问题，就是在数组这种最基础的结构中处理问题的，今天主要介绍 LeetCode 中典型的数组类问题，主要介绍这类问题的一些常用解法：做好初始定义；基础算法思想应用；对撞指针；滑动窗口法等。所有题解代码采用 Python 实现。

做好初始定义

做数组类算法问题的时候，我们常常需要定义一个变量，明确该变量的定义，并且在书写整个逻辑的时候，要不停的维护住这个变量的意义。也特别需要注意初始值和边界的问题。

283. 移动零（前往该题）

题目描述

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
示例：
输入: [0,1,0,3,12]

输出: [1,3,12,0,0]

说明：
  • 必须在原数组上操作，不能拷贝额外的数组。
  • 尽量减少操作次数。

直观解题思路

首先遍历一遍数列，用另个数列按顺序存储所有非 0 的元素，在将存储的非零元素按顺序复制到原数列中，空位补 0 即可。
直观的解题思路新建额外的数组，不符合要求，但是对于我们下面的优化算法很有起始。

简单的优化

只要把数组中所有的非零元素，按顺序给数组的前段元素位赋值，剩下的全部直接赋值 0。我们定义一个 nums 0...i 表示为非 0 元素的数组，之后在遍历数列的时候不断维护这个定义.

代码实现

classSolution:
  defmoveZeroes(self,nums):
    """
      :type nums: List[int]
      :rtype: void Do not return anything, modify nums in-place instead.
"""
    n =len(nums)
    i =-1
    j =0
    # nums[0....i]表示非0元素的数列,初始值i=-1
    while j <= n-1:
      if nums[j]!=0:
        i +=1
        nums[i]= nums[j]
      j +=1
    for k inrange(i+1, n):
      nums[k]=0

相似问题：

27. 移除元素（前往该题）

题目描述

给定一个数组 nums 和一个值 val，你需要原地移除所有数值等于 val 的元素，返回移除后数组的新长度。不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
示例 1:
给定 nums =[3,2,2,3], val =3,
函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。
你不需要考虑数组中超出新长度后面的元素。
...

解题思路

定义 nums[0...i] 为非 val 的数列，遍历整个数列不断的维护这个定义

代码实现

classSolution:
  defremoveElement(self,nums,val):
    """
    :type nums: List[int]
    :type val: int
    :rtype: int
"""
    n =len(nums)
    i =-1
    # 定义nums[0...i]为非val的数列
    j =0
    while j <= n-1:
      if nums[j]!= val:
        i +=1
        nums[i]= nums[j]
      j +=1
    return i+1

26. 删除排序数组中的重复项（前往该题）

题目描述

给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。
示例 1:
给定数组 nums =[1,1,2],
函数应该返回新的长度 2, 并且原数组 nums 的前两个元素被修改为 1,2。
你不需要考虑数组中超出新长度后面的元素。
...

解题思路

定义 nums[0...i] 为为非重复数列，遍历整个数列不断的维护这个定义。

代码实现

classSolution:
  defremoveDuplicates(self,nums):
    """
    :type nums: List[int]
    :rtype: int
"""
    n =len(nums)
    if n ==0or n ==1:
      return n
    # nums[0,i]为非重复数列
    i =0
    j = i +1
    while j <= n-1:
      if nums[j]!= nums[i]:
        # 指向同一个元素不需要赋值
        if i +1!= j:
          nums[i+1]= nums[j]
        i +=1
      j +=1
    return i +1

80. 删除排序数组中的重复项 II（前往该题）

题目描述

给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素最多出现两次，返回移除后数组的新长度。不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。
示例 1:
给定 nums =[1,1,1,2,2,3],
函数应返回新长度 length =5, 并且原数组的前五个元素被修改为 1,1,2,2,3 。
你不需要考虑数组中超出新长度后面的元素。

解题思路

定义 nums[0...i] 满足每个元素最多出现两次，初始值 i=-1，遍历整个数列不断的维护这个定义。

代码实现

classSolution:
  defremoveDuplicates(self,nums):
    """
    :type nums: List[int]
    :rtype: int
"""
    n =len(nums)
    if(n <=2):
      return n
    # nums[0...i]是符合要求的，
    i =1
    k = i -1
    j = i +1
    while j <= n-1:
      if(nums[j]!= nums[i])or(nums[j]== nums[i]and nums[j]!= nums[k]):
        k = i
        nums[i+1]= nums[j]
        i +=1
      j +=1
    return i +1

基础算法思想在leetcode中的应用

典型的排序算法思想、二分查找思想在解 LeetCode 题目时很有用。

75. 颜色分类（前往该题）

题目描述

给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
注意:
不能使用代码库中的排序函数来解决这道题。
示例:
输入:[2,0,2,1,1,0]
输出:[0,0,1,1,2,2]
...

解题思路

基数排序法
可以采用基数排序法的思想，用一个数组记录下 0，1，3 的次数，后重排，这个算法对数组进行了两次遍历，其实有一种只进行一次遍历的方法。
三路快速排序方法
设置三个 lt, gt, i 定义：nums[0...lt] == 0，nums[lt+1...i-1] = 1，nums[gt...n-1] == 2，遍历一遍改数列保持这个定义。

代码实现

classSolution:
  defsortColors(self,nums):
    n =len(nums)
    lt =-1
    gt = n
    i =0
    while i < gt:
      if nums[i]==0:
        lt +=1
        nums[lt], nums[i]= nums[i], nums[lt]
        i +=1
      elif nums[i]==2:
        gt -=1
        nums[gt], nums[i]= nums[i], nums[gt]
      else:
        i +=1

215. 数组中的第 K 个最大元素（前往该题）

题目描述

在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
示例 1:
输入:[3,2,1,5,6,4] 和 k =2
输出:5
...

解题思路

利用快速排序的思想，从数组 S 中随机找出一个元素 X，把数组分为两部分 Sa 和 Sb。Sa 中的元素大于等于 X，Sb 中元素小于 X。这时有两种情况：
  • Sa 中元素的个数小于 k，则 Sb 中的第 k-|Sa| 个元素即为第k大数；
  • Sa 中元素的个数大于等于 k，则返回 Sa 中的第 k 大数。时间复杂度近似为 O(n)

代码实现

classSolution:
  # 采用快速排序方法，分成的数列左边大于右边
  deffindKthLargest(self,nums,k):
    n =len(nums)
    if(k > n):
      return
    index =self.quickSort(nums,0, n-1, k)
    return nums[index]
  defquickSort(self,nums,l,r,k):
    if l >= r:
      return l
    p =self.partition(nums, l, r)
    if p +1== k:
      return p
    if p +1> k:
      returnself.quickSort(nums, l, p -1, k)
    else:
      returnself.quickSort(nums, p +1, r, k)
  defpartition(self,nums,l,r):
    v = nums[l]
    j = l
    i = l +1
    while i <= r:
      if nums[i]>= v:
        nums[j+1],nums[i]= nums[i],nums[j+1]
        j +=1
      i +=1
    nums[l], nums[j]= nums[j], nums[l]
    return j

相似问题：

88. 合并两个有序数组（
前往该题
）

题目描述

给定两个有序整数数组 nums1 和 nums2，将 nums2 合并到 nums1 中，使得 num1 成为一个有序数组。
说明:
  • 初始化 nums1 和 nums2 的元素数量分别为 m 和 n。
  • 你可以假设 nums1 有足够的空间（空间大小大于或等于 m + n）来保存 nums2 中的元素。
...

解题思路

常规解题思路
其实这道题就是归并排序 partition 的过程(将两个有序的数列合并成一个有序数列)， 直观的思路是新建一个新的数列，遍历 nums1 和 nums2 这两个数列，将新建的数列有序后又赋值给 nums1 后返回。其实还有一种方法不需要开辟新的空间。
尾插法
由于 nums1 有足够的空间（空间大小大于或等于 m + n）来保存 nums2 中的元素，所以从 k=m+n-1 开始，分别遍历 nums1[m...0] 和 nums2[n...0] 中选取值大的。

代码实现

classSolution:
  defmerge(self,nums1,m,nums2,n):
    # 尾插入法
    if(n <1):
      return
    if(m <1):
      nums1[0:n]= nums2[0:n]
      return
    k = m + n -1
    i = m -1
    j = n -1
    while k >=0:
      if(nums1[i]> nums2[j]and i >=0)or(j <0and i >=0):
        nums1[k]= nums1[i]
        k -=1
        i -=1
      if(nums2[j]>= nums1[i]and j >=0)or(i <0and j >=0):
        nums1[k]= nums2[j]
        k -=1
        j -=1

双索引技术-对撞指针

有一些 LeetCode 题目，我们可以采用对撞指针进行求解：指针 i 和 j 分别指向数组的第一个元素和最后一个元素，然后指针 i 不断向前， 指针 j 不断递减，知道 i = j（当然具体的逻辑操作根据题目的变化而变化）。

167. 两数之和 II - 输入有序数组（前往该题）

题目描述

给定一个已按照升序排列 的有序数组，找到两个数使得它们相加之和等于目标数。 函数应该返回这两个下标值 index1 和 index2，其中 index1 必须小于 index2。
说明:
  • 返回的下标值（index1 和 index2）不是从零开始的。
  • 你可以假设每个输入只对应唯一的答案，而且你不可以重复使用相同的元素。
...

暴力解法

双层遍历，时间复杂度为 O(n^2)，暴力解法没有充分利用原数组的性质 —— 有序，本文不采用。
当我们看到数列有序的时候，就应该想到可以用二分搜索法

二分搜索法

遍历每个 nums[i]，在剩余数组中查找 target-nums[i] 的值，时间复杂度为 O(n log n)。
有兴趣的读者可以用这种方法尝试一下，应该也是可以AC的， 本文采用对撞指针法。

对撞指针法

们首先判断首尾两项的和是不是 target，如果比 target 小，那么我们左边 (i)+1 位置的数（比左边位置的数大）再和右相相加，继续判断。如果比 target 大，那么我们右边 (j)-1 位置的数（比右边位置的数小）再和左相相加，继续判断。我们通过这样不断放缩的过程，就可以在 O(n) 的时间复杂度内找到对应的坐标位置。

代码实现

classSolution:
  deftwoSum(self,numbers,target):
    n =len(numbers)
    if(n <2):
      return[]
    i =0
    j = n-1
    while i < j:
      if numbers[i]+ numbers[j]== target:
        return[i+1,j+1]
      elif numbers[i]+ numbers[j]< target:
        i +=1
      else:
        j -=1
    return[]

相似问题：

125. 验证回文串（前往该题）

题目描述

给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。
说明：本题中，我们将空字符串定义为有效的回文串。
...

解题思路

采用对撞指针

代码实现

classSolution:
  defisPalindrome(self,s):
    """
    :type s: str
    :rtype: bool
"""
    n =len(s)
    i =0
    j = n-1
    while i < j:
      if s[i].isalnum()==False:
        i +=1
        continue
      if s[j].isalnum()==False:
        j -=1
        continue
      if s[i].lower()!= s[j].lower():
        returnFalse
      i +=1
      j -=1
    returnTrue
注：isalnum() 判断一个字符是否为数字或者字母，lower() 字符转小写函数。

345. 反转字符串中的元音字母（前往该题）

题目描述

编写一个函数，以字符串作为输入，反转该字符串中的元音字母。
示例 1：
给定 s ="hello", 返回 "holle".
示例 2：
给定 s ="leetcode", 返回 "leotcede".
注意:
元音字母不包括 "y".

解题思路

也是采用对撞指针

代码实现

classSolution:
  defreverseVowels(self,s):
    """
    :type s: str
    :rtype: str
"""
    ss =list(s)
    aeiou =['a','e','i','o','u','A','E','I','O','U']
    n =len(s)
    i =0
    j = n-1
    while i < j:
      if ss[i]notin aeiou:
        i +=1
        continue
      if ss[j]notin aeiou:
        j -=1
        continue
      if(i < j):
        ss[i], ss[j]= ss[j], ss[i]
      i +=1
      j -=1
    d =''
    return d.join(ss)

11. 盛最多水的容器（前往该题）

题目描述

给定 n 个非负整数 a1，a2，...，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
图示

解题思路

我们在由线段长度构成的数组中使用两个指针，一个放在开始，一个置于末尾。 此外，我们会使用变量 maxarea 来持续存储到目前为止所获得的最大面积。 在每一步中，我们会找出指针所指向的两条线段形成的区域，更新 maxarea，并将指向较短线段的指针向较长线段那端移动一步。

代码实现

classSolution:
  defmaxArea(self,height):
    """
    :type height: List[int]
    :rtype: int
"""
    n =len(height)
    i =0
    j = n -1
    maxarea =(j - i)*min(height[i], height[j])
    while i < j:
      if height[i]< height[j]:
        i +=1
      else:
        j -=1
      maxarea =max(maxarea,(j - i)*min(height[i], height[j]))
    return maxarea

双索引技术-滑动窗口

一些题目用滑动窗口方法解题，可以将时间复杂度控制在 O(n) 级别，最重要的是定义好滑动窗口，明确它要表达的意思，当然边界和初始值非常重要。

209. 长度最小的子数组（前往该题）

题目描述

给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的长度最小的连续子数组。如果不存在符合条件的连续子数组，返回 0。
...

解题思路

要求是连续子数组，所以我们必须定义 i，j两个指针，i 向前遍历，j 向后遍历，相当与一个滑块，这样所有的子数组都会在 [i...j] 中出现，如果 nums[i..j] 的和小于目标值 s，那么j向后移一位，再次比较，直到大于目标值 s 之后，i 向前移动一位，缩小数组的长度。遍历到i到数组的最末端，就算结束了，如果不存在符合条件的就返回 0。

代码实现

classSolution:
  defminSubArrayLen(self,s,nums):
    """
    :type s: int
    :type nums: List[int]
    :rtype: int
"""
    n =len(nums)
    if(n <1orsum(nums)< s):
      return0
    # 维护一个滑动窗口nums[i,j], nums[i...j] < s
    i =0
    j =-1
    total =0
    res = n +1
    while i <= n-1:
      if(j +1< n)and total < s:
        j +=1
        total += nums[j]
      else:
        total -= nums[i]
        i +=1
      if(total >= s):
        res =min(res, j-i+1)
    if res == n+1:
      return0
    return res

总结

我们知道在准备面试的时候，刷算法题是一种捷径，特别是刷 LeetCode，但是不能一味的刷题，我们需要总结和思考，对于一些相似的题目我们应该多想想他们的思想，其实很多题的解题思路都是相近的。
继续阅读
阅读原文