当前位置：首页 > web >正文

LeetCode-数组技巧题目

web 2025/7/22 12:09:05

数组题目技巧总结

二分查找

确保区间不变量，保持左闭右闭

如果middle的值已经比target小了，那么这个middle值一定不等于target，也就是target一定在middle的右面，所以left=middle+1

        while(left<=right){//防止出现两个很大的数字相加之后溢出int middle=(right-left)/2+left;if(nums[middle]<target){left=middle+1;}else if(nums[middle]>target){right=middle-1;}else{return middle;}}

移除元素

使用好快慢指针，fast指针寻找需要放在新数组的元素，slow指针对应这个元素在新数组的下标

        int slow=0;for(int fast=0;fast<nums.length;fast++){//如果当前fast指向的数组元素不等于VAL，那么就要放在slow下表对应的新数组位置中if(nums[fast]!=val){nums[slow++]=nums[fast];}}

滑动窗口

遍历一遍终点指针，在这过程中更新初始指标，按照最小或者最大去更新滑动窗口的长度，主要注意left指针怎么移动，以及怎么判断这一次的初始指针移动结束

class Solution {public int minSubArrayLen(int target, int[] nums) {int left=0;int sum=0;int result=Integer.MAX_VALUE;for(int right=0;right<nums.length;right++){sum+=nums[right];while(sum>=target){//更新遍历初始指针条件，更新滑动窗口长度result=Math.min(result,right-left+1);sum-=nums[left++];}}return result==Integer.MAX_VALUE ? 0 : result;}
}

模拟行为

把握住循环不变量，遇见螺旋矩阵，对于四边的遍历操作一定要统一规则

class Solution {public int[][] generateMatrix(int n) {//确定四边边界值，往中间逼近int[][] result=new int[n][n];int top=0;int right=n-1;int bottom=n-1;int left=0;int count=1;while(count<=n*n){int a=left;while(count<=n*n && a<right){result[top][a++]=count;count++;}int b=top;while(count<=n*n && b<bottom){result[b++][right]=count;count++;}int c=right;while(count<=n*n && c>left){result[bottom][c--]=count;count++;}            int d=bottom;while(count<=n*n && d>top){result[d--][left]=count;count++;}if(top==bottom && left==right){result[top][left]=count;count++;}top++;bottom--;left++;right--;}return result;}
}

螺旋的三道题都可以用四个边界指针进行逼近。

前缀和

下面的两道题目，计算区间，区间差值，很好用，数组的内容就这些了，继续努力。

977.有序数组的平方（左右双指针）

给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。

示例 1：

输入：nums = [-4,-1,0,3,10]
输出：[0,1,9,16,100]
解释：平方后，数组变为 [16,1,0,9,100]
排序后，数组变为 [0,1,9,16,100]

示例 2：

输入：nums = [-7,-3,2,3,11]
输出：[4,9,9,49,121]提示：

1 <= nums.length <= 104
-104 <= nums[i] <= 104
nums 已按 非递减顺序 排序

class Solution {public int[] sortedSquares(int[] nums) {//新建一个数组，双指针每次扫描一个最大的元素放进这个数组里面int n=nums.length;int[] result=new int[n];//定义数组的长度l=n-1int k=n-1;//最终要放满数组int left=0;int right=k;while(k>=0){int ltwo=nums[left]*nums[left];int rtwo=nums[right]*nums[right];if(ltwo<rtwo){result[k--]=rtwo;right--;}else{result[k--]=ltwo;left++;}}return result;}
}

由于题目中有负数也有正数，最终要用平方进行非递减排序，我们可以想象最左侧和最右侧永远有一个最大的或者两个一样最大的。
有了这个思路我们就可以用双指针left和right向中间逼近，由于没有空间复杂度的要求，我们可以新建一个空数组，将左右两边最大的放入这个空数组中。
while循环的终止条件是装满数组，用新数组长度下标大于等于0作为判断条件就可以。
移除元素相关的数组题目思想是快慢双指针，这道题是左右两端向中间逼近的双指针

区间和（利用数组的前缀和）

import java.util.Scanner;public class Main
{public static void main(String[] args){Scanner sc = new Scanner(System.in);//计算区间常用 前缀和int n=sc.nextInt();//保留前缀和建立一个数组int[] pre=new int[n];int presum=0;for(int i=0;i<n;i++){int input=sc.nextInt();presum+=input;pre[i]=presum;}//hasNextInt（）是一个 Java 中的 Scanner 类的方法，用于检查输入流中是否还有一个整数。如果输入流中还有一个整数，该方法将返回 true；否则返回 falsewhile(sc.hasNextInt()){int x=sc.nextInt();int y=sc.nextInt();if(x==0){System.out.println(pre[y]);}else{System.out.println(pre[y]-pre[x-1]);}}}
}

熟悉一下ACM的输入格式，从psvm到sout手敲一遍
假设输入的五行数字为1,2,3,4,5 那么pre[1]和pre[3]就等于3和10，记录当前下标对应的值和之前的值的和，就是pre数组存放的元素。
这道题的案例求1到3的区间和，也就是2+3+4，那么就相当于pre[3]-pre[0]，去掉原数组的第一个元素
利用scanner.hasNextInt来获取后面的若干组区间和，如果区间和的左区间x为0，那么直接输出pre[y]就可以，因为pre[0]包含了第一个元素。其余情况输出pre[y]-pre[x-1]

开发商购买土地（利用数组前缀和）

import java.util.Scanner;public class Main{public static void main(String[] args){Scanner sc=new Scanner(System.in);int n=sc.nextInt();int m=sc.nextInt();//方便作差，计算总和sum，往最小更新，result设为最大值int sum=0;int result=Integer.MAX_VALUE;int[][] block=new int[n][m];for(int i=0;i<n;i++){for(int j=0;j<m;j++){block[i][j]=sc.nextInt();sum+=block[i][j];}}//横向分的最小值和纵向分的最小值取最小值//横向分int[] prerow=new int[n];for(int i=0;i<n;i++){for(int j=0;j<m;j++){prerow[i]+=block[i][j];}}//纵向分int[] precol=new int[m];for(int i=0;i<m;i++){for(int j=0;j<n;j++){precol[i]+=block[j][i];}}//更新最小值int rowsum=0;for(int i=0;i<n;i++){rowsum+=prerow[i];result=Math.min(result,Math.abs((sum-rowsum)-rowsum));           }//纵向分更新最小值int colsum=0;for(int i=0;i<m;i++){colsum+=precol[i];result=Math.min(result,Math.abs((sum-colsum)-colsum)); }System.out.println(result);}
}

重点在于更新最小值更新的是什么值，是当前横向分或者纵向分，取的一部分（前缀和）和另一部分的差值最小。前缀和很容易得到，那么差值就是用总和减去当前部分（得到另一部分）再减去当前部分取绝对值abs（得到差值）
理解差值怎么获取了，就声明一个最大变量result，然后在输入n行m列元素的时候计算一下总和sum。
横向和纵向的前缀和分别建立一个一维数组，遍历数组的每一行相加、遍历数组的每一列相加得到
然后就遍历横向划分更新结果，再遍历纵向划分更新结果，最终System.out.println(result)输出结果

查看全文

http://www.xdnf.cn/news/9612.html