刷题1：数组篇

---

作者有话说

  1、本篇是算法刷题系列文章的第一篇，写此系列的目的是为了让自己对题目的理解更加深刻。

  2、本系列博客主要参考了卡哥的 代码随想录博客 以及 卡哥本人B站讲解的视频 代码随想录B站视频 ，强烈推荐给大家，因为本人学习中 Python为主，因此博客主要由 Python 代码呈现给大家，需要其他语言的版本，卡哥博客链接自取。

---

一、数组介绍

  数组是存放在连续内存空间上的相同类型数据的集合，需要两点注意的是：1、数组下标都是从0开始的；2、数组内存空间的地址是连续的；3、数组的元素是不能删的，只能覆盖。。

二、相关题目

2.1 LeetCode704 二分查找

• 题目原址： 704. 二分查找
• 题目描述： 给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。
• 解题思路： 本题主要是考察二分法，其算法思想是：取数组中间值mid，区间 [left，right] 大小是数组大小。每次使用 中间值mid 去进行判断，若大了，修改 right的值 ，若小了，修改 left的值 ，若相等则返回。使用二分法的前提：数组有序，数组内无重复元素 。
• 代码如下：

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        left = 0
        right = len(nums) - 1
        while left <= right:
            mid = left + (right - left) // 2
            if nums[mid] > target:
                right = mid - 1
            elif nums[mid] < target:
                left = mid + 1
            else:
                return mid
        return -1
1
2
3
4
5
6
7
8
9
10
11
12
13

2.2 LeetCode27 移除元素

• 题目原址： 27. 移除元素
• 题目描述： 给你一个数组 nums 和一个值 val，你需要 原地移除 所有数值等于 val 的元素，并 返回移除后数组的新长度 。
• 解题思路： 题目要求是原地移除，我们采用 双指针 方法中的快慢指针去操作，慢指针 slow 控制“所谓的新数组”，快指针 fast 去遍历原数组；通过条件判断将满足题意的值给到 slow 所控制的“新数组”，最终返回 slow 的值，就是“新数组的长度”。
• 代码如下：

class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        if nums is None or len(nums)==0: 
            return 0 
        slow = 0
        for fast in range(0, len(nums)):
            if nums[fast] != val:
                nums[slow] = nums[fast]
                slow += 1
        return slow
1
2
3
4
5
6
7
8
9
10

2.3 LeetCode977 有序数组的平方

• 题目原址： 977. 有序数组的平方
• 题目描述： 给你一个按 非递减顺序 排序的整数数组 nums ，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。
• 解题思路：

法1、暴力求解： 计算出数组每个值的平方值，然后再排序即可，代码不再给出；
法2、双指针法： 根据题意知，数组其实是有序的， 只不过负数平方之后可能成为最大数了。那么数组平方的最大值就在数组的两端，不是最左边就是最右边，不可能是中间。此时可以考虑双指针法了，i 指向起始位置，j 指向终止位置。定义一个新数组 result ，和 A 数组一样的大小，让 k 指向 result 数组终止位置。
$$\begin{gathered} 如果A[i]\ast A[i]<A[j]\ast A[j]，那么result[k--]=A[j]\ast A[j] \\ 如果A[i]\ast A[i]>=A[j]\ast A[j]，那么result[k--]=A[i]\ast A[i] \end{gathered}$$。

• 代码如下：

class Solution:
    def sortedSquares(self, nums: List[int]) -> List[int]:
        # 双指针
        n = len(nums)
        result = [-1] * n
        i, j, k = 0, n - 1, n - 1

        while i <= j:
            i_2 = nums[i] * nums[i]
            j_2 = nums[j] * nums[j]

            if i_2 < j_2:
                result[k] = j_2
                j -= 1
            else:
                result[k] = i_2
                i += 1
            k -= 1
        return result
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

2.4 LeetCode209 长度最小的子数组

• 题目原址： 209. 长度最小的子数组
• 题目描述： 给定一个含有 n 个正整数的数组和一个正整数 target 。找出 该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。
• 解题思路：

法1、暴力求解： 双层for循环遍历数组，然后找到大于等于target的最小数组区间的长度；
法2、滑动窗口法【双指针】： 滑动窗口其实也是双指针，就是不断的调节子序列的起始位置和终止位置，从而得出我们要想的结果。在本题中实现滑动窗口，主要确定如下三点：

• 窗口内是什么？满足其和 ≥ target 的长度最小的 连续 子数组。
• 如何移动窗口的起始位置？如果当前窗口的值大于 target 了，窗口就要向前移动了（也就是该缩小了）。
• 如何移动窗口的结束位置？窗口的结束位置就是遍历数组的指针，也就是for循环里的索引。

• 代码如下：
  法一：暴力求解

# 法一：暴力求解
class Solution:
    def minSubArrayLen(self, s: int, nums: List[int]) -> int:
        # 定义一个无限大的数
        res = float("inf")
        Sum = 0
        index = 0
        for i in range(len(nums)):
            Sum += nums[i]
            while Sum >= s:
                res = min(res, i-index+1)
                Sum -= nums[index]
                index += 1
        return 0 if res==float("inf") else res
1
2
3
4
5
6
7
8
9
10
11
12
13
14

法二：滑动窗口

# 法二：滑动窗口
class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        if nums is None or len(nums) == 0: 
            return 0 
        lenf = len(nums) + 1
        total = 0
        i = j = 0
        while (j < len(nums)):
            total = total + nums[j]
            j += 1
            while (total >= target):
                lenf = min(lenf, j - i)
                total = total - nums[i]
                i += 1
        if lenf == len(nums) + 1:
            return 0
        else: 
            return lenf
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

2.4.1 推荐题目

1. LeetCode904 水果成篮
2. LeetCode76 最小覆盖子串

三、参考资料

• 二分法
• 尺取法、双指针、滑动窗口

---

总结

  数组篇到这里就结束了，里面涉及的例题并不是很多，大家可以针对文章中提到的算法继续练习，链表篇见吧。