笔试leetcode算法题-数组
从今天开始更新一些做过的leetcode经典算法题啦，会尽量按照算法类型更新，也方便自己大家查看
1.数组题常考类型
2. 常用解题思路
2.1 双指针
-
快慢指针：用于原地删除元素、检测环等。
-
左右指针夹逼：用于排序数组中求和、区间收缩。
-
滑动窗口：动态维护区间满足条件。
2.2 前缀和 / 差分
-
前缀和：
prefix[i] = sum(nums[0..i-1])，O(1) 查询任意区间和。 -
哈希优化前缀和：用于统计满足条件的子数组个数。
-
差分数组：快速区间加减，适合批量更新。
2.3 排序 + 组合技巧
-
排序后配合双指针，去重、快速收缩范围。
-
注意：排序会改变原数组顺序，若题目要求保持原顺序需谨慎。
2.4 单调栈 / 单调队列
-
单调递增栈：找下一个更小元素。
-
单调递减栈：找下一个更大元素。
-
常用于 O(n) 求解区间最值、最大面积等。
2.5 动态规划
-
状态设计：明确
dp[i]含义（子数组、子序列、二维 DP）。 -
转移方程：找出状态间的递推关系。
-
初始化和边界条件：不要漏处理
i=0或j=0。
2.6 二分查找
-
适用于有序数组或单调性问题。
-
注意区分 查找元素 vs 查找插入位置。
3. 常见注意点
-
边界条件
-
数组为空 / 长度为 1。
-
区间端点 off-by-one 错误（
<=vs<）。
-
-
重复元素处理
-
去重逻辑（跳过相邻重复元素）。
-
-
溢出问题
-
求和或乘积时可能超过
int范围，用long。
-
-
原地操作与空间复杂度
-
是否允许额外空间，O(1) 操作要小心顺序。
-
-
排序副作用
-
如果题目要求保留原顺序，不要直接排序。
-
-
时间复杂度要求
-
面试时先确认期望复杂度再选方法（如 O(n^2) 可接受？）。
-
4. 高频模板（伪代码）
双指针求和类
Arrays.sort(nums);for (int i = 0; i 0 && nums[i] == nums[i - 1]) continue; int l = i + 1, r = n - 1; while (l < r) { int sum = nums[i] + nums[l] + nums[r]; if (sum == target) { /* 处理结果 */ } else if (sum < target) l++; else r--; }}滑动窗口
int left = 0, sum = 0;for (int right = 0; right target) { sum -= nums[left++]; } // 根据题意更新答案}前缀和 + 哈希
Map map = new HashMap();map.put(0, 1);int sum = 0, count = 0;for (int num : nums) { sum += num; if (map.containsKey(sum - k)) { count += map.get(sum - k); } map.put(sum, map.getOrDefault(sum, 0) + 1);}4.leetcode题目
704二分查找
class Solution { public int search(int[] nums, int target) { int left =0; int right = nums.length -1; while(left <= right ){ //如果right能取到最后一位，[leftm right]那么left==right也是成立的 int mid = (right-left) /2 +left; if(nums[mid] == target){ return mid; }else if(nums[mid] < target){ left = mid+1; // mid已经确定不相等了，肯定要+1 }else{ right = mid-1; } } return -1; }}27移除元素
给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。
不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并原地修改输入数组。
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
示例 1: 给定 nums = [3,2,2,3], val = 3, 函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。 你不需要考虑数组中超出新长度后面的元素。
示例 2: 给定 nums = [0,1,2,2,3,0,4,2], val = 2, 函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。
你不需要考虑数组中超出新长度后面的元素。
class Solution { public int removeElement(int[] nums, int val) { //这种移动的可以用快慢指针 int slow = 0; for(int fast =0; fast < nums.length; fast++){ //找到第一个不是val的值赋给slow if(nums[fast] != val){ nums[slow] = nums[fast]; slow++; } } return slow; }}
