数组算法总结：搭配leetcode经典题型，教你完全掌握与数组相关的算法（包括java C++ go python版本）

Ne0inhk

— 11 min read

一、二分查找（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)），核心是用两个指针分工：

  1. 慢指针（slow）：记录「非 val 元素」的存放位置，初始为 0；
  2. 快指针（fast）：遍历整个数组，逐个检查元素，初始为 0；
  3. 遍历过程中，若快指针指向的元素 ≠ val，则将该元素赋值给慢指针位置，慢指针右移；若等于 val，则快指针直接跳过；
  4. 遍历结束后，慢指针的位置（索引）就是非 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 大）。因此：

  1. 初始化左指针 left 指向数组开头，右指针 right 指向数组末尾；
  2. 初始化结果数组 res，长度和原数组一致，用一个指针 k 从末尾向前填充（先放最大的平方值）；
  3. 比较 nums[left] 和 nums[right] 的绝对值：
    • 若 |nums[left]| > |nums[right]|，则将 nums[left]² 放入 res[k]，左指针右移；
    • 否则将 nums[right]² 放入 res[k]，右指针左移；
  4. 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 res

Java

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 长度最小的子数组）

核心解题思路（滑动窗口 / 双指针）

滑动窗口的核心是用两个指针维护一个「动态窗口」，通过扩张和收缩窗口找到满足条件的最小长度：

  1. 右指针（right）：扩张窗口，逐个将元素加入窗口，累加窗口内元素和；
  2. 左指针（left）：当窗口和≥target 时，收缩窗口（左指针右移），并更新最小窗口长度；
  3. 遍历结束后，若找到有效窗口则返回最小长度，否则返回 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 0

Java

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 }

五、总结

这四种算法是操作数组常用的算法也是面试和笔试中常考的算法，这四种算法能应用于大部分操作数组的情景，最后祝读者的算法学习之路一帆风顺！文章如有错误欢迎私信我，我会及时解决，如果我的内容对你有帮助和启发，请点赞、评论、收藏。你们的支持就是我更新最大的动力，那么我们下期再见！

Read more

【C++---哈希表】哈希表的魅力，不仅在于其高效与便捷，更在于其背后所蕴含的深刻哲理。它告诉我们，即使面对再复杂、再混乱的世界，只要我们用心去寻找、去创造，总能找到一种方法，将其变得有序而美好。

【C++---哈希表】哈希表的魅力，不仅在于其高效与便捷，更在于其背后所蕴含的深刻哲理。它告诉我们，即使面对再复杂、再混乱的世界，只要我们用心去寻找、去创造，总能找到一种方法，将其变得有序而美好。

哈希表 * 1 unordered_map和unordered_set的使⽤ * 1.1 unordered_set和unordered_multiset参考⽂档 * 1.2 unordered_set类的介绍 * 1.3unordered_set和set的差异 * 1.4 unordered_map和map的使⽤差异 * 2 哈希表实现 * 2.1 哈希概念 * 2.2 直接定址法 * 2.3 哈希冲突 * 2.4 负载因子 * 2.5 将关键字转为整数 * 2.6 哈希函数 * 2.6.1 哈希函数之除法散列法 * 2.7 哈希的防御措施

By Ne0inhk
《C++ 动态规划》第001-002题：第N个泰波拉契数，三步问题

《C++ 动态规划》第001-002题：第N个泰波拉契数，三步问题

🔥个人主页：Cx330🌸 ❄️个人专栏：《C语言》《LeetCode刷题集》《数据结构-初阶》《C++知识分享》 《优选算法指南-必刷经典100题》《Linux操作系统》:从入门到入魔 《Git深度解析》:版本管理实战全解 🌟心向往之行必能至 🎥Cx330🌸的简介： 目录 前言： 01.第N个泰波拉契数 算法原理（动态规划）： 思路： 解法代码（C++）： 博主手记（字体还请见谅哈）： 02.三步问题 算法原理（动态规划）： 思路： 解法代码（C++）： 博主手记（字体还请见谅哈）： 结尾： 前言： 聚焦算法题实战，系统讲解三大核心板块：“精准定位最优解”——优选算法，“简化逻辑表达，系统性探索与剪枝优化”——递归与回溯，“以局部最优换全局高效”——贪心算法，讲解思路与代码实现，帮助大家快速提升代码能力 01.

By Ne0inhk
Flutter for OpenHarmony：diffutil_dart 列表差异计算引擎，高性能 UI 局部刷新的秘密武器（Myers 算法） 深度解析与鸿蒙适配指南

Flutter for OpenHarmony：diffutil_dart 列表差异计算引擎，高性能 UI 局部刷新的秘密武器（Myers 算法） 深度解析与鸿蒙适配指南

欢迎加入开源鸿蒙跨平台社区：https://openharmonycrossplatform.ZEEKLOG.net 前言 在 Flutter 开发中，我们经常遇到列表更新的场景： * 用户下拉刷新，服务器返回了新的 20 条数据，其中 18 条是旧的，2 条是新的，还有 1 条被删除了。 * 我们需要更新 ListView 或 SliverList。 直接调用 setState 重新构建整个 List 确实简单，但性能有损耗，而且会导致 Scroll 位置丢失、动画生硬。我们希望能够： * 只插入那 2 条新数据。 * 只移除那 1 条旧数据。 * 并伴随优雅的插入/移除动画（使用 AnimatedList）。 diffutil_dart 就是解决这个问题的算法库。

By Ne0inhk