数组算法总结：搭配leetcode经典题型，教你完全掌握与数组相关的算法（包括java C++ go python版本）
一、二分查找（leetcode702 二分查找）
给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果 target 存在返回下标，否则返回 -1。
你必须编写一个具有 O(log n) 时间复杂度的算法。
二分查找是一个非常经典的操作数组的算法，其使用的条件是必须是一个有序的数组（升序或降序），其核心是根据数组的有序性来将target与nums[mid]比较，若target>nums[mid],则target在mid的右边区间，否则在左半区间，搞清楚这个问题后，那么代码就非常容易写出来了。
python
def search(nums: list[int], target: int) -> int: # 初始化左闭右闭区间 [left, right] left, right = 0, len(nums) - 1 # 区间有效时继续循环（左闭右闭区间，left <= right 才有效） while left <= right: # 计算中间索引，避免 (left + right) 溢出（Python无溢出，但养成通用习惯） mid = left + (right - left) // 2 if nums[mid] == target: return mid # 找到目标，返回索引 elif nums[mid] < target: left = mid + 1 # 目标在右半区，左边界右移（排除mid） else: right = mid - 1 # 目标在左半区，右边界左移（排除mid） return -1 # 未找到目标 Java
public class BinarySearch { public static int search(int[] nums, int target) { // 初始化左闭右闭区间 [left, right] int left = 0; int right = nums.length - 1; // 区间有效时循环 while (left <= right) { // 计算mid，避免 int 溢出（Java中int最大值约2e9，left+right可能溢出） int mid = left + (right - left) / 2; if (nums[mid] == target) { return mid; // 找到目标 } else if (nums[mid] < target) { left = mid + 1; // 目标在右半区 } else { right = mid - 1; // 目标在左半区 } } return -1; // 未找到 } C++
#include <iostream> #include <vector> using namespace std; int search(vector<int>& nums, int target) { // 初始化左闭右闭区间 [left, right] int left = 0; int right = nums.size() - 1; // 区间有效时循环 while (left <= right) { // 计算mid，避免溢出 int mid = left + (right - left) / 2; if (nums[mid] == target) { return mid; // 找到目标 } else if (nums[mid] < target) { left = mid + 1; // 目标在右半区 } else { right = mid - 1; // 目标在左半区 } } return -1; // 未找到 } package main import "fmt" func search(nums []int, target int) int { // 初始化左闭右闭区间 [left, right] left, right := 0, len(nums)-1 // 区间有效时循环 for left <= right { // 计算mid，避免溢出（Go中int随系统，64位系统无溢出，但保持通用） mid := left + (right - left) / 2 if nums[mid] == target { return mid // 找到目标 } else if nums[mid] < target { left = mid + 1 // 目标在右半区 } else { right = mid - 1 // 目标在左半区 } } return -1 // 未找到 }由于该题目的区间是闭区间，因此中间的值是可以取到的，在一般的实际情况中，最常见的是左闭右开区间即[left,right)，其中间值则无法取到，因此循环条件会发生改变，即只需要改成while(left<right)即可，因为left==right无意义。将left=mid+1改为left=mid+1,right=mid-1即可，代码不再赘述。
二、快慢指针（leetcode27 移除元素）
给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素。元素的顺序可能发生改变。然后返回 nums 中与 val 不同的元素的数量。
假设 nums 中不等于 val 的元素数量为 k，要通过此题，您需要执行以下操作：
- 更改
nums数组，使nums的前k个元素包含不等于val的元素。nums的其余元素和nums的大小并不重要。 - 返回
k。
这道题如果使用暴力解法直接遍历每个区间，时间复杂度为O（n*n）其在leetcode上是可以通过的，但是此题还有一个更为高效的方法，那就是快慢指针。
核心解题思路（快慢指针法）
这是本题的最优解法（时间复杂度 O (n)，空间复杂度 O (1)），核心是用两个指针分工：
- 慢指针（slow）：记录「非 val 元素」的存放位置，初始为 0；
- 快指针（fast）：遍历整个数组，逐个检查元素，初始为 0；
- 遍历过程中，若快指针指向的元素 ≠ val，则将该元素赋值给慢指针位置，慢指针右移；若等于 val，则快指针直接跳过；
- 遍历结束后，慢指针的位置（索引）就是非 val 元素的数量 k。
这种方法无需删除元素，仅通过「覆盖」实现原地修改，完全满足题目要求。
python
def removeElement(nums: list[int], val: int) -> int: # 慢指针：初始指向第一个位置（非val元素的存放位置） slow = 0 # 快指针：遍历整个数组 for fast in range(len(nums)): # 快指针找到非val元素，赋值给慢指针位置 if nums[fast] != val: nums[slow] = nums[fast] slow += 1 # 慢指针右移，准备存下一个非val元素 # 慢指针的最终值就是非val元素的数量 return slow Java
public class RemoveElement { public static int removeElement(int[] nums, int val) { // 慢指针初始为0 int slow = 0; // 快指针遍历数组 for (int fast = 0; fast < nums.length; fast++) { // 快指针找到非val元素，赋值给慢指针位置 if (nums[fast] != val) { nums[slow] = nums[fast]; slow++; // 慢指针右移 } } // 返回非val元素数量 return slow; }C++
#include <iostream> #include <vector> using namespace std; int removeElement(vector<int>& nums, int val) { // 慢指针初始为0 int slow = 0; // 快指针遍历数组 for (int fast = 0; fast < nums.size(); fast++) { // 快指针找到非val元素，赋值给慢指针位置 if (nums[fast] != val) { nums[slow] = nums[fast]; slow++; // 慢指针右移 } } // 返回非val元素数量 return slow; }go
package main import "fmt" func removeElement(nums []int, val int) int { // 慢指针初始为0 slow := 0 // 快指针遍历数组 for fast := 0; fast < len(nums); fast++ { // 快指针找到非val元素，赋值给慢指针位置 if nums[fast] != val { nums[slow] = nums[fast] slow++ // 慢指针右移 } } // 返回非val元素数量 return slow }三、双指针（Leetcode997 有序数组的平方）
给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。
这道题最容易想到的思路就是先将每个数组中的元素进行平方，然后再进行排序，这种思路是最简单的。下面介绍一个更高效的方法：双指针。
核心解题思路（双指针法）
原数组是非递减的，但包含负数，平方后最大的值一定出现在数组的两端（如 -5 平方是 25，比 3 平方的 9 大）。因此：
- 初始化左指针
left指向数组开头，右指针right指向数组末尾； - 初始化结果数组
res，长度和原数组一致，用一个指针k从末尾向前填充（先放最大的平方值）； - 比较
nums[left]和nums[right]的绝对值：- 若
|nums[left]| > |nums[right]|，则将nums[left]²放入res[k]，左指针右移； - 否则将
nums[right]²放入res[k]，右指针左移；
- 若
k向前移动一位，直到左右指针相遇，最终res就是非递减的平方数组。
python
def sortedSquares(nums: list[int]) -> list[int]: n = len(nums) res = [0] * n # 初始化结果数组 left, right = 0, n - 1 # 左右指针 k = n - 1 # 结果数组的填充指针（从后往前） while left <= right: # 比较两端元素的绝对值 left_sq = nums[left] **2 right_sq = nums[right]** 2 if left_sq > right_sq: res[k] = left_sq left += 1 # 左指针右移 else: res[k] = right_sq right -= 1 # 右指针左移 k -= 1 # 填充指针左移 return resJava
public class SortedSquares { public static int[] sortedSquares(int[] nums) { int n = nums.length; int[] res = new int[n]; // 初始化结果数组 int left = 0, right = n - 1; // 左右指针 int k = n - 1; // 填充指针 while (left <= right) { int leftSq = nums[left] * nums[left]; int rightSq = nums[right] * nums[right]; if (leftSq > rightSq) { res[k] = leftSq; left++; } else { res[k] = rightSq; right--; } k--; } return res; }C++
#include <iostream> #include <vector> using namespace std; vector<int> sortedSquares(vector<int>& nums) { int n = nums.size(); vector<int> res(n); // 初始化结果数组 int left = 0, right = n - 1; // 左右指针 int k = n - 1; // 填充指针 while (left <= right) { int leftSq = nums[left] * nums[left]; int rightSq = nums[right] * nums[right]; if (leftSq > rightSq) { res[k] = leftSq; left++; } else { res[k] = rightSq; right--; } k--; } return res; }go
package main import "fmt" func sortedSquares(nums []int) []int { n := len(nums) res := make([]int, n) // 初始化结果数组 left, right := 0, n-1 // 左右指针 k := n - 1 // 填充指针 for left <= right { leftSq := nums[left] * nums[left] rightSq := nums[right] * nums[right] if leftSq > rightSq { res[k] = leftSq left++ } else { res[k] = rightSq right-- } k-- } return res }四、滑动窗口（Leetcode209 长度最小的子数组）
核心解题思路（滑动窗口 / 双指针）
滑动窗口的核心是用两个指针维护一个「动态窗口」，通过扩张和收缩窗口找到满足条件的最小长度：
- 右指针（right）：扩张窗口，逐个将元素加入窗口，累加窗口内元素和；
- 左指针（left）：当窗口和≥target 时，收缩窗口（左指针右移），并更新最小窗口长度；
- 遍历结束后，若找到有效窗口则返回最小长度，否则返回 0。
python
def minSubArrayLen(target: int, nums: list[int]) -> int: n = len(nums) min_len = float('inf') # 初始化为无穷大，记录最小长度 left = 0 # 左指针，窗口左边界 current_sum = 0 # 窗口内元素和 for right in range(n): # 右指针扩张窗口 current_sum += nums[right] # 窗口和≥target时，收缩左指针，优化最小长度 while current_sum >= target: min_len = min(min_len, right - left + 1) # 更新最小长度 current_sum -= nums[left] # 左指针右移，移出窗口 left += 1 # 若min_len仍为无穷大，说明无符合条件的子数组，返回0；否则返回min_len return min_len if min_len != float('inf') else 0Java
public class MinSubArrayLen { public static int minSubArrayLen(int target, int[] nums) { int n = nums.length; int minLen = Integer.MAX_VALUE; // 初始化为整型最大值 int left = 0; // 左指针 int currentSum = 0; // 窗口和 for (int right = 0; right < n; right++) { // 右指针扩张 currentSum += nums[right]; // 收缩左指针，优化最小长度 while (currentSum >= target) { minLen = Math.min(minLen, right - left + 1); currentSum -= nums[left]; left++; } } // 无符合条件的子数组返回0，否则返回minLen return minLen == Integer.MAX_VALUE ? 0 : minLen; }C++
#include <iostream> #include <vector> #include <climits> // 包含INT_MAX using namespace std; int minSubArrayLen(int target, vector<int>& nums) { int n = nums.size(); int minLen = INT_MAX; // 初始化为整型最大值 int left = 0; // 左指针 int currentSum = 0; // 窗口和 for (int right = 0; right < n; right++) { // 右指针扩张 currentSum += nums[right]; // 收缩左指针，优化最小长度 while (currentSum >= target) { minLen = min(minLen, right - left + 1); currentSum -= nums[left]; left++; } } // 无符合条件的子数组返回0，否则返回minLen return minLen == INT_MAX ? 0 : minLen; }go
package main import ( "fmt" "math" ) func minSubArrayLen(target int, nums []int) int { n := len(nums) minLen := math.MaxInt32 // 初始化为int32最大值 left := 0 // 左指针 currentSum := 0 // 窗口和 for right := 0; right < n; right++ { // 右指针扩张 currentSum += nums[right] // 收缩左指针，优化最小长度 for currentSum >= target { if right - left + 1 < minLen { minLen = right - left + 1 } currentSum -= nums[left] left++ } } // 无符合条件的子数组返回0，否则返回minLen if minLen == math.MaxInt32 { return 0 } return minLen }五、总结
这四种算法是操作数组常用的算法也是面试和笔试中常考的算法，这四种算法能应用于大部分操作数组的情景，最后祝读者的算法学习之路一帆风顺！文章如有错误欢迎私信我，我会及时解决，如果我的内容对你有帮助和启发，请点赞、评论、收藏。你们的支持就是我更新最大的动力，那么我们下期再见！
