一文了解什么是数组及其经典考察题目

前言

一文带你了解数组的基础，并且其经常考察的思维算法。本文用于记录自己的学习过程，同时向大家进行分享相关的内容。本文内容参考于代码随想录同时包含了自己的许多学习思考过程，如果有错误的地方欢迎批评指正！

数组

数组理论基础

什么是是数组？数组就是存放在计算机连续空间上的相同类型数据的集合。其便利性在于我们可以直接通过数组下标访问其元素，但也正是因为其连续存储的特性，我们需要对其实现增删操作的时候需要连续处理其他的元素。

数组的特性：

数组的下标是从0开始的

数组的存储空间是连续的

修改数组元素的方式是覆盖而不是直接删除其地址

数组的经典考察的题目

二分法

理论

应用场景：当存在一个有序数组且无重复元素的（以升序为例），我们需要从中找到我们想要的元素的位置该怎么办最简单？

首先我们当然可以遍历整个数组，一个一个比较找到元素的位置，但是这样处理未免太过麻烦，同时最坏的情况下的时间复杂度为O(n).

这个时候我们看其题目的特性，其是一个有序的数组，且无重复元素。那我们可以每次比较其中间值，当中间值比该元素大的时候，说明其肯定在中间值的左半区间，反之则肯定在右半区间。该方法处理的时间复杂度为O(logn)

其思想很简单，也很容易实现，但是其最经常困扰大家的一个问题就是边界带不带等号的问题，即到底是while(left

其实无论是while(left

我们来看，当判断条件是while(left

这里使用的是<,其left=right在区间内是没有意义的，那么我们每次比较完target之后呢，if (nums[middle] > target) right 更新为 middle，因为当前nums[middle]不等于target，为什么这样，因为我们已经比较过了其nums[middle]的值是不符合我们需要的，而我们是从左闭右开的区间去找，那我们更新right就应该令right 更新为 middle，倘若更新为middle-1，我们未比较过nums[middle-1]是不是等于target的，所以就是会出现问题的。

其实现代码为（这里为python代码）：

class Solution:

def search(self, nums: List[int], target: int) -> int:

left, right = 0, len(nums) # 定义target在左闭右开的区间里，即：[left, right)

while left < right: # 因为left == right的时候，在[left, right)是无效的空间，所以使用 <

middle = left + (right - left) // 2

if nums[middle] > target:

right = middle # target 在左区间，在[left, middle)中

elif nums[middle] < target:

left = middle + 1 # target 在右区间，在[middle + 1, right)中

else:

return middle # 数组中找到目标值，直接返回下标

return -1 # 未找到目标值

当判断条件是while(left<=right)时，其实质就是从[left,right] 左闭右闭区间去找符合要求的值

同理来看这里使用的是=，其left=right在区间内是有意义的，那么我们每次比较完target之后呢，if (nums[middle] > target) right 更新为 middle-1，因为当前nums[middle]不等于target，为什么这样，因为我们已经比较过了其nums[middle]的值是不符合我们需要的，而我们是从左闭右闭的区间去找，那我们更新right就应该令right 更新为 middle-1。

其实现代码为（这里为python代码）：

class Solution:

def search(self, nums: List[int], target: int) -> int:

left, right = 0, len(nums) - 1 # 定义target在左闭右闭的区间里，[left, right]

while left <= right:

middle = left + (right - left) // 2

if nums[middle] > target:

right = middle - 1 # target在左区间，所以[left, middle - 1]

elif nums[middle] < target:

left = middle + 1 # target在右区间，所以[middle + 1, right]

else:

return middle # 数组中找到目标值，直接返回下标

return -1 # 未找到目标值

实战练手

本题目来源于力扣

其解答为：

class Solution:

def searchInsert(self, nums: List[int], target: int) -> int:

left,right=0,len(nums)-1

while (left<=right):

middle=(left+right)//2

if target>nums[middle]:

left+=1

elif target

right-=1

else:

return middle

return left

双指针法

理论

应用场景：给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并原地修改输入数组。元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

最直接的方法就是两个for循环，一个for循环用来找值为val的，一个for循环用来移动数组位置。最直接的方法当然会更加复杂，其时间复杂度为O($n^2$).

当然我们也可以用双指针法，用一个for循环来完成两个for循环的事情。其时间复杂度为O(n)

首先定义快慢指针：

快指针：用来寻找值不为val的元素

慢指针：用来更新新数组的下标

其含义一定要理解。具体什么意思：fast一直在数组循环，当找到值不为val的元素，就与slow交换，当fast遍历完整个数组，那么slow所代表的数组以内就都会是符合要求的值了。

其实现代码为：

class Solution:

def removeElement(self, nums: List[int], val: int) -> int:

# 快慢指针

fast = 0 # 快指针

slow = 0 # 慢指针

size = len(nums)

while fast < size: # 不加等于是因为，a = size 时，nums[a] 会越界

# slow 用来收集不等于 val 的值，如果 fast 对应值不等于 val，则把它与 slow 替换

if nums[fast] != val:

nums[slow] = nums[fast]

slow += 1

fast += 1

return slow

实战

本题目来源于力扣

其实现为：

class Solution:

def removeDuplicates(self, nums: List[int]) -> int:

slow,fast=0,1

while fast

if nums[slow]!=nums[fast]:

nums[slow+1]=nums[fast]

slow=slow+1

fast+=1

return slow+1

滑动窗口法

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

这道题目暴力解法当然是 两个for循环，然后不断的寻找符合条件的子序列，时间复杂度很明显是O($n^2$)。

主要讲述滑动窗口法，其实其思想有些类似于双指针法。其核心就是不断的调节子序列的起始位置和终止位置，从而得出我们要想的结果。对于这道题，我们首先定义其left和right，让right一直向右移动累加，直至出现满足题意要求的区间，当然若是超出数组范围其无直接返回0.当出现满足题意区间后，left移动，缩小区间看是否能够继续满足，满足则继续移动。当不满足时，right开始向右移动，一直进行，直至right到达边界并且区间最小时终止。

其实现代码为：

class Solution:

def minSubArrayLen(self, s: int, nums: List[int]) -> int:

l = len(nums)

left = 0

right = 0

min_len = float('inf')

cur_sum = 0 #当前的累加值

while right < l:

cur_sum += nums[right]

while cur_sum >= s: # 当前累加值大于目标值

min_len = min(min_len, right - left + 1)

cur_sum -= nums[left]

left += 1

right += 1

return min_len if min_len != float('inf') else 0

前缀和法

应用场景：给定一个整数数组 Array，请计算该数组在每个指定区间内元素的总和。

此题何解？使用前缀和法，非常巧妙。当然我们可以直接一个for循环从指定区间加完即可，但是当有特别多特别多的区间需要去求和的时候怎么办，每次都是从头加一遍，会浪费大量的计算内存，因为其出现的很多都是重复过的计算。所以前缀和法出现了，我们使用另一个数组用来记录其下标前的所有总和，当求区间时直接该数组的对应下标的元素相减即可。

其实现代码为：

import sys

input = sys.stdin.read

def main():

data = input().split()

index = 0

n = int(data[index])

index += 1

vec = []

for i in range(n):

vec.append(int(data[index + i]))

index += n

p = [0] * n

presum = 0

for i in range(n):

presum += vec[i]

p[i] = presum

results = []

while index < len(data):

a = int(data[index])

b = int(data[index + 1])

index += 2

if a == 0:

sum_value = p[b]

else:

sum_value = p[b] - p[a - 1]

results.append(sum_value)

for result in results:

print(result)

if __name__ == "__main__":

main()