Algorithms
KMP算法
muchen
问题：如果给定文本串S“BBC ABCDAB ABCDABCDABDE”，和模式串P“ABCDABD”，
现在要拿模式串P去跟文本串S匹配，如果文本串中含有模式串，则返回出现的
位置，若没有则返回-1.
可以使用暴力解法，代码如下(暴力易懂，但是重复比较次数太多)：
public class VoilenceMatch {
public static void main(String[] args) {
String s1 = "basadbace";
String s2 = "bac";
System.out.println( new VoilenceMatch().voilenceMatch(s1, s2));
}
public int voilenceMatch(String s1,String s2) {
char[] c1 = s1.toCharArray();
char[] c2 = s2.toCharArray();
int i = 0;
int j = 0;
while(i < c1.length && j < c2.length) {
if (c1[i] == c2[j]) {
i++;
j++;
}else {
i = i - (j - 1);
j = 0;
}
}
if(j == c2.length) {
return i - j;
}else {
return -1;
}
}
}
使用KMP算法解决该问题(思路)
寻找前缀后缀最长公共元素长度(最大长度表)
对于P = p0 p1 …pj-1 pj，寻找模式串P中长度最大且相等的前缀和后缀。如果存在p0 p1 …pk-1 pk = pj- k pj-k+1…pj-1 pj，那么在包含pj的模式串中有最大长度为k+1的相同前缀后缀。举个例子， 如果给定的模式串是：“ABCDABD”，从左至右遍历整个模式串，其各个子串的前缀后缀分别如下表格所示：
基于《最大长度表匹配》
给定文本串“BBC ABCDAB ABCDABCDABDE”，和模式串“ABCDABD”，现在要拿模式串去跟文本串匹配，如下图所示：
因为模式串中的字符A跟文本串中的字符B、B、C、空格一开始就不匹配，所以不必考虑结论，直接将模式串不断的右移一位即可，直到模式串中的字符A跟文本串的第5个字符A匹配成功：
继续往后匹配，当模式串最后一个字符D跟文本串匹配时失配，显而易见，模式串需要向右移动。但向右移动多少位呢？因为此时已经匹配的字符数为6个（ABCDAB)，然后根据《最大长度表》可得失配字符D的上一位字符B对应的长度值为2，所以根据之前的结论，可知需要向右移动6 - 2 = 4 位。
模式串向右移动4位后，发现C处再度失配，因为此时已经匹配了2个字符（AB），且上一位字符B对应的最大长度值为0，所以向右移动：2 - 0 =2 位。
A与空格失配，向右移动1 位。
继续比较，发现D与C 失配，故向右移动的位数为：已匹配的字符数6减去上一位字符B对应的最大长度2，即向右移动6 - 2 = 4 位.
经历第5步后，发现匹配成功，过程结束。
KMP代码实现
public class KMPAlgorithm {
public static void main(String[] args) {
String str1 = "BBC ABCDAB ABCDABCDABDE";
String str2 = "ABCDABD";
KMPAlgorithm kmpAlgorithm = new KMPAlgorithm();
// System.out.println(Arrays.toString(kmpAlgorithm.getNext(str2)));
int[] next = kmpAlgorithm.getNext(str2);
System.out.println(kmpAlgorithm.kmpSearch(str1, str2, next));
}
//实现KMP算法 需传入父串、子串、
public int kmpSearch(String str1,String str2,int[] next) {
for(int i = 0,j = 0;i < str1.length();i++) {
if (j > 0 && str1.charAt(i) != str2.charAt(j)) {
j = next[j-1];
}
if (str1.charAt(i) == str2.charAt(j)) {
j++;
}
if (j == str2.length()) {
return i-j+1;
}
}
return -1;
}
//获得子串的对应的next数组
//即原模式串子串对应的各个前缀后缀的公共元素的最大长度表 简称《最大长度表》
public int[] getNext(String string) {
char[] array = string.toCharArray();
int[] next = new int[array.length];
next[0] = 0;
for(int j = 0,i = 1;i < next.length;i++) {
//KMP算法核心：
//当子串中元素不相等时
if (j > 0 && array[i]!=array[j]) {
j = next[j-1];
}
//当子串中两个元素相等时
if(array[i] == array[j]) {
j++;
}
next[i] = j;
}
return next;
}
}
斐波那契数列
1 1 2 3 5 8 13....第一个和第二个数字是1，其他的数字等于前两个数字之和
递归实现：
例一
/**
* @author muchen
* @create 2023 - 02 - 2023/2/18 11:22
* 斐波那契数列的实现
*/
public class FeiBoNaQi {
public static void main(String[] args) {
// 递归：代码简洁，但是涉及到的运算会随着递归层数的增加成指数级增长
System.out.println(count(50));
}
public static int count(int n){
// 斐波那契数列的前两位为1
if (n == 1||n == 2){
return 1;
}
return count(n - 1)+count(n-2);
}
}
例二
(20年Java蓝桥杯)
如下图所示，小明用从1开始的正整数"蛇形"填充无限大的矩阵。
1 2 6 7 15 16 28 29...
3 5 8 14 17 27 30...
4 9 13 18 26 31...
10 12 19 25 32...
11 20 24 33...
21 23 34...
22 35...
容易看出矩阵第二行第二列中的数是5。请你计算矩阵中第20行第20列的数是多少?
分析：第20行20列处于45度这条线上，
这条线上的数字是：1,5,13,25,41.... 两数之差：4 8 12 16...
每一个都是在前一个数之差的基础上+4，可以用递归或者循环
且第20行20列相当于这个数列的第20位数字
/**
* @author muchen
* @create 2023 - 02 - 2023/2/18 14:47
*/
public class Snake {
public static void main(String[] args) {
System.out.println(count(20));
}
public static int count(int n){ //n=20时结果为761
if (n == 1){
return 1;
}
return (n - 1)*4+count(n - 1); //通过递归计算前一个数的值
}
}
回溯解决全排列问题
问题1：
输入格式 输入一个整数 n 。
* 输出格式 每行输出一种方案。
* 同一行内的数必须升序排列，相邻两个数用恰好 1 个空格隔开。
* 对于没有选任何数的方案，输出空行。
* 本题有自定义校验器（SPJ），各行（不同方案）之间的顺序任意。
* 输入样例： 3
* 输出样例：
*
* 3
* 2
* 2 3
* 1
* 1 3
* 1 2
* 1 2 3
注意：使用集合存放遍历之后的结果，每遍历到一个节点处即输出结果。
回溯的思想即为：将遍历的过程看作一个树，在递归过程中，每遍历一个数据就将其放入集合中去，并在下一次存放数据之前将该结果输出出来。如果数组满了将集合中的最后一个数据弹出，并结束此次递归过程，进入上层递归。
public class Main_1 {
LinkedList<Integer> temp = new LinkedList<Integer>();
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
//输入
int num = scanner.nextInt();
new Main_1().backTracking(1, num);
for(int i = 1; i<=num;i++) {
System.out.print(i+" ");
}
}
public void backTracking(int startIndex, int num) {
if(temp.size()==num) {
return;
}
for(int i:temp) {
System.out.print(i+" ");
}
System.out.println();
for(int i = startIndex;i <=num;i++) {
temp.add(i); //将遍历到的元素放入temp集合中
backTracking(i+1, num); //递归寻找下一个元素
temp.removeLast(); //回溯的实现
}
}
}
题目2：
* 小蓝有一条玩具蛇，一共有 16 节，上面标着数字 1 至 16。每一节都是一 个正方形的形状。 相邻的两节可以成直线或者成 90 度角。 小蓝还有一个
* 4× 4 的方格盒子， 用于存放玩具蛇，盒子的方格上依次标着 字母 A 到 P 共 16 个字母。
* 小蓝可以折叠自己的玩具蛇放到盒子里面。他发现，有很多种方案可以将 玩具蛇放进去。 请帮小蓝计算一下，总共有多少种不同的方案。如果两个方案中，存在玩
* 具蛇的某一节放在了盒子的不同格子里，则认为是不同的方案。
//每一格子都得遍历四个方位,必须用回溯解决
public class Main_E {
static boolean[][] booles = new boolean[4][4];// true表示已经遍历过
static int result = 0;
static int[] dx = new int[] { 0, 1, 0, -1 };
static int[] dy = new int[] { -1, 0, 1, 0 };
public static void main(String[] args) {
for (int i = 0; i < 4; i++) {
for (int j = 0; j < 4; j++) {
booles[i][j] = true;
backTracking(i, j, 0);
booles[i][j] = false;
}
}
System.out.println(result);
}
public static void backTracking(int x, int y, int index) {
if (index == 15) {
result++;
return;
}
for (int i = 0; i < 4; i++) {
int xi = x + dx[i], yi = y + dy[i];
//判断是否越界
if (xi >= 0 && xi < 4 && yi >= 0 && yi < 4 && !booles[xi][yi]) {
booles[xi][yi] = true;
backTracking(xi, yi, index + 1);
booles[xi][yi] = false;// 回溯
}
}
}
}
BFS解决迷宫问题(经典题目)
迷宫问题：
题目描述：
阿尔吉侬是一只聪明又慵懒的小白鼠，它最擅长的就是走各种各样的迷宫。
* 今天它要挑战一个非常大的迷宫，研究员们为了鼓励阿尔吉侬尽快到达终点，就在终点放了一块阿尔吉侬最喜欢的奶酪。
* 现在研究员们想知道，如果阿尔吉侬足够聪明，它最少需要多少时间就能吃到奶酪。
* 迷宫用一个 R×C 的字符矩阵来表示。
* 字符 S 表示阿尔吉侬所在的位置，字符 E 表示奶酪所在的位置，字符 # 表示墙壁，字符 . 表示可以通行。
* 阿尔吉侬在 1 个单位时间内可以从当前的位置走到它上下左右四个方向上的任意一个位置，但不能走出地图边界。
* 输入格式 第一行是一个正整数 T ，表示一共有 T 组数据。
* 每一组数据的第一行包含了两个用空格分开的正整数 R 和 C ，表示地图是一个 R×C 的矩阵。
* 接下来的 R 行描述了地图的具体内容，每一行包含了 C 个字符。字符含义如题目描述中所述。保证有且仅有一个 S 和 E。
* 输出格式 对于每一组数据，输出阿尔吉侬吃到奶酪的最少单位时间。
* 若阿尔吉侬无法吃到奶酪，则输出“oop!”（只输出引号里面的内容，不输出引号）。
* 每组数据的输出结果占一行。
* 数据范围 1<T≤10 , 2≤R,C≤200
* 输入样例：
* 3
* 3 4
* .S..
* ###.
* ..E.
* 3 4
* .S..
* .E..
* ....
* 3 4
* .S..
* ####
* ..E.
* 输出样例： 5 1 oop!
BFS算法：通过队列的形式每遍历一个节点就将其上下左右四个方向可以通行的节点放入到集合中，并将其对应的dis[] [] 中存放的数值加（这也是BFS可以寻找迷宫最短路径的原因）。算法直到 符合终止条件 或者遍历到迷宫最后一个方格时停止，因为此时除了墙壁之外都遍历过，即dis[] [] != -1
dis[] [] 的作用：1.存放最短路径 2.初始置为-1表示未走过，通过遍历将每个位置的值相对于上一个位置的值加1.
public class Main_7 {
static final int N = 210;
static char[][] map = new char[N][N];//存放迷宫地图
static int[][] dis = new int[N][N];//存储起点到每个路径的长度
static Loc start,end;
static int R,C;
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int T = scanner.nextInt();
while(T-- > 0) {
R = scanner.nextInt();
C = scanner.nextInt();
for(int i = 0;i<R;i++) {
map[i] = scanner.next().toCharArray();
}
for(int i =0;i<R;i++) {
for(int j = 0;j<C;j++) {
if(map[i][j]=='S') start=new Loc(i,j);
if(map[i][j]=='E') end = new Loc(i,j);
}
}
int result = dfs(start,end);
if(result!=-1) System.out.println(result);
else System.out.println("oop!");
}
scanner.close();
}
private static int dfs(Loc start, Loc end) {
Queue<Loc> queue = new LinkedList<>();
//将dis所有元素置为-1，表示未走过.
for(int i = 0;i<N;i++) Arrays.fill(dis[i], -1);
dis[start.x][start.y] = 0;
queue.offer(start);
int[] dx = new int[] {-1,0,1,0};
int[] dy = new int[] {0,1,0,-1};
while(queue.size()!=0) {
Loc t = queue.poll();//取出队列首位元素，并删除
for(int i =0;i<4;i++) {
int x = t.x+dx[i],y= t.y+dy[i];
if(x<0||x>=R||y<0||y>=C) continue;//出界
if(map[x][y]=='#') continue;//墙壁
if(dis[x][y]!=-1) continue;//之前已经遍历过
dis[x][y] = dis[t.x][t.y] + 1;//能走到这一点则步数加1
//在入队的时候判断是否找到重点，找到返回dis[x][y];
if(end.x == x && end.y == y) return dis[x][y];
//将新状态加入队尾
queue.offer(new Loc(x, y));
}
}
return -1;
}
}
class Loc{
int x;
int y;
public Loc(int x, int y) {
super();
this.x = x;
this.y = y;
}
}
BFS解决扩散问题
题目：
* 小蓝在一张无限大的特殊画布上作画。 这张画布可以看成一个方格图，每个格子可以用一个二维的整数坐标表示。
* 小蓝在画布上首先点了一下几个点：(0, 0),
* (2020, 11), (11, 14), (2000, 2000)。 只有这几个格子上有黑色，其它位置都是白色的。
* 每过一分钟，黑色就会扩散一点。具体的，如果一个格子里面是黑色，它 就会扩散到上、下、左、右四个相邻的格子中，使得这四个格子也变成黑色
* （如果原来就是黑色，则还是黑色）。 请问，经过 2020 分钟后，画布上有多少个格子是黑色的。
//bfs宽搜
public class Main_B {
static final int N = 10000;
static int[][] dis = new int[N][N];//存放哪些点被遍历过
static char[][] map = new char[N][N];
static int[] dx = new int[] {0,1,0,-1};
static int[] dy = new int[] {-1,0,1,0};
public static void main(String[] args) {
int res = 0;
for(int i=0;i<N;i++) {
for(int j=0;j<N;j++) {
if(i==3000&&j==3000) map[i][j] = '*';
else if(i==5020&&j==3011) map[i][j] = '*';
else if(i==3011&&j==3014) map[i][j] = '*';
else if(i==5000&&j==5000) map[i][j] = '*';
else map[i][j]='.';//将坐标系上的黑点记为*，白点记为.
}
}
bfs();
for(int i = 0;i<N;i++) {
for(int j=0;j<N;j++) {
if(map[i][j]=='*') {
res++;
}
}
}
System.out.println(res);
}
private static void bfs() {
for(int i=0;i<N;i++) Arrays.fill(dis[i], -1);//将距离数组全部记为-1；即未遍历过
dis[3000][3000] = 0;
dis[5020][3011] = 0;
dis[3011][3014] = 0;
dis[5000][5000] = 0;
Queue<Pii> queue = new LinkedList<Pii>();
queue.offer(new Pii(3000, 3000));
queue.offer(new Pii(5020, 3011));
queue.offer(new Pii(3011, 3014));
queue.offer(new Pii(5000, 5000));
while(queue.size()!=0) {
Pii temp = queue.poll();
if(dis[temp.x][temp.y]==2020) return;
for(int i=0;i<4;i++) {
int a=temp.x+dx[i],b=temp.y+dy[i];
if(map[a][b]=='*') continue;//已经是黑色
if(dis[a][b]!=-1) continue;//已经走过
if(a < 0 || a > 10000 || b < 0 || b > 10000) continue;
map[a][b] = '*';
dis[a][b]=dis[temp.x][temp.y]+1;
queue.offer(new Pii(a, b));
}
}
}
}
class Pii {
//创建一个类用于存放棋盘坐标
int x;
int y;
public Pii(int x, int y) {
super();
this.x = x;
this.y = y;
}
}
BFS中的fill flood算法
问题3：
* 你有一张某海域 N×N 像素的照片，”.”表示海洋、”#”表示陆地，如下所示：
*
* .......
*
* .##....
*
* .##....
*
* ....##.
*
* ..####.
*
* ...###.
*
* .......
*
* 其中”上下左右”四个方向上连在一起的一片陆地组成一座岛屿，例如上图就有 2 座岛屿。
*
* 由于全球变暖导致了海面上升，科学家预测未来几十年，岛屿边缘一个像素的范围会被海水淹没。
*
* 具体来说如果一块陆地像素与海洋相邻(上下左右四个相邻像素中有海洋)， 它就会被淹没。
*
* 例如上图中的海域未来会变成如下样子：
*
* ....... ....... ....... ....... ....#.. ....... .......
* 请你计算：依照科学家的预测，照片中有多少岛屿会被完全淹没。
*
* 输入格式 第一行包含一个整数N。
*
* 以下 N 行 N 列，包含一个由字符”#”和”.”构成的 N×N 字符矩阵，代表一张海域照片，”#”表示陆地，”.”表示海洋。
*
* 照片保证第 1 行、第 1 列、第 N 行、第 N 列的像素都是海洋。
*
* 输出格式 一个整数表示答案
public class Main_7 {
static final int N = 1010;
static int result = 0;
static int num;
static char[][] map = new char[N][N];
static boolean[][] bool = new boolean[N][N];
static int[] dx = new int[] { -1, 0, 1, 0 };
static int[] dy = new int[] { 0, 1, 0, -1 };
public static void main(String[] args) {
Scanner scanner = new Scanner(new BufferedInputStream(System.in));
num = scanner.nextInt();
for (int i = 0; i < num; i++) {
map[i] = scanner.next().toCharArray();
}
for (int i = 0; i < num; i++) {
for (int j = 0; j < num; j++) {
if (map[i][j] == '#' && !bool[i][j]) {
if(bfs(i, j)) result++;
}
}
}
System.out.println(result);
}
private static boolean bfs(int i, int j) {
Queue<Pii> queue = new LinkedList<Pii>();
queue.offer(new Pii(i, j));
int total = 0,bound = 0;
bool[i][j] = true;//表示已经枚举过
while(queue.size()!=0) {
Pii poll = queue.poll();
total++;
boolean isbound = false;
for(int m=0;m<4;m++) {
int a = poll.x+dx[m];
int b = poll.y+dy[m];
if(a<0&&a>num&&b<0&&b>num) continue;
if(bool[a][b]) continue;
if(map[a][b]=='.') {
isbound=true;
continue;
}
queue.offer(new Pii(a, b));
bool[a][b] = true;
}
if (isbound) {
bound++;
}
}
return total==bound;
}
}
class Pii {
int x;
int y;
public Pii(int x, int y) {
super();
this.x = x;
this.y = y;
}
}
贪心算法
题目：
* 小明正在玩一个“翻硬币”的游戏。
*
* 桌上放着排成一排的若干硬币。我们用 * 表示正面，用 o 表示反面（是小写字母，不是零）。
*
* 比如，可能情形是：**oo***oooo
*
* 如果同时翻转左边的两个硬币，则变为：oooo***oooo
*
* 现在小明的问题是：如果已知了初始状态和要达到的目标状态，每次只能同时翻转相邻的两个硬币,那么对特定的局面，最少要翻动多少次呢？
*
* 我们约定：把翻动相邻的两个硬币叫做一步操作。
*
* 输入格式 两行等长的字符串，分别表示初始状态和要达到的目标状态。
* 示例1： *o**o***o***
*o***o**o***
输出： 1
示例2：**********
o****o****
输出：5
public class Main_4 {
static char[] start_chars;
static char[] end_chars;
static int result = 0;
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
start_chars = scanner.nextLine().toCharArray();//输入初始状态
end_chars = scanner.nextLine().toCharArray();//需达到的状态
for(int i=0;i<start_chars.length-1;i++) {//从左向右遍历
//如果遍历到i的位置不符合最终状态，则反转i和i+1的硬币
if (start_chars[i]!=end_chars[i]) {
exchange(i);
result++;
}
}
System.out.println(result);
}
public static void exchange(int i) {
if (start_chars[i]=='*') {
start_chars[i]='o';
}else {
start_chars[i]='*';
}
if (start_chars[i+1]=='*') {
start_chars[i+1]='o';
}else {
start_chars[i+1]='*';
}
}
}
dp（动态规划）
题目：
* 小蓝特别喜欢单调递增的事物。 在一个字符串中，如果取出若干个字符，将这些字符按照在字符串中的顺
* 序排列后是单调递增的，则成为这个字符串中的一个单调递增子序列。 例如，在字符串 lanqiao 中，如果取出字符 n 和 q，则 nq 组成一个单
* 调递增子序列。类似的单调递增子序列还有 lnq、i、ano 等等。 小蓝发现，有些子序列虽然位置不同，但是字符序列是一样的，例如取第
* 二个字符和最后一个字符可以取到 ao，取最后两个字符也可以取到 ao。小蓝 认为他们并没有本质不同。
* 对于一个字符串，小蓝想知道，本质不同的递增子序列有多少个？ 例如，对于字符串 lanqiao，本质不同的递增子序列有 21 个。它们分别 是
* l、a、n、q、i、o、ln、an、lq、aq、nq、ai、lo、ao、no、io、lnq、 anq、lno、ano、aio。 请问对于以下字符串（共
* 200 个小写英文字母，分四行显示）：（如果你把 以下文字复制到文本文件中，请务必检查复制的内容是否与文档中的一致。 tocyjkdzcieoiodfpbgcncsrjbhmugdnojjddhllnofawllbhf
* iadgdcdjstemphmnjihecoapdjjrprrqnhgccevdarufmliqij
* gihhfgdcmxvicfauachlifhafpdccfseflcdgjncadfclvfmad
* vrnaaahahndsikzssoywakgnfjjaihtniptwoulxbaeqkqhfwl 本质不同的递增子序列有多少个？
//动态规划解决该问题
/*
* 1
* l
*
* 11
* la (a<l)所以a只有自身一个
*
* 11(1+1+1)
* lan n:n>a&&n>l 所以n的递增子序列有3个
*/
public class Main_D {
public static void main(String[] args) {
String s1 = "tocyjkdzcieoiodfpbgcncsrjbhmugdnojjddhllnofawllbhf"
+ "iadgdcdjstemphmnjihecoapdjjrprrqnhgccevdarufmliqij"
+ "gihhfgdcmxvicfauachlifhafpdccfseflcdgjncadfclvfmad"
+ "vrnaaahahndsikzssoywakgnfjjaihtniptwoulxbaeqkqhfwl";
// String s1 = "lanqiao";
char[] charArray = s1.toCharArray();
int dp[] = new int[charArray.length];//用于存放第i个字母的递增子序列有多少个
Arrays.fill(dp, 1);
for(int i=1;i<charArray.length;i++) {
for(int j=0;j<i;j++) {
if (charArray[j]<charArray[i]) {
dp[i]+=dp[j];
}
if (charArray[i]==charArray[j]) {
// dp[i]=dp[j];
// dp[j]=0;
dp[i]=0;
}
}
}
long sum = 0;
for(int i = 0;i<dp.length;i++) sum+=dp[i];
System.out.println(sum);
}
}
前缀和的应用
题目1：
* 给定一个长度为 n 的数组 a1,a2,…,an 。
*
* 现在，要将该数组从中间截断，得到三个非空子数组。
*
* 要求，三个子数组内各元素之和都相等。
*
* 请问，共有多少种不同的截断方法？
*
* 输入格式 第一行包含整数 n 。
*
* 第二行包含 n 个整数 a1,a2,…,an 。
*
* 输出格式 输出一个整数，表示截断方法数量。
*
* 数据范围 前六个测试点满足 1≤n≤10 。 所有测试点满足 1≤n≤105 ， −10000≤ai≤10000 。
*
* 输入样例1： 4 1 2 3 3 输出样例1： 1
阶段和相等数组的思想：即切两刀将数组分为三段。我们先切割第二刀，并通过重置第二刀的位置来确定到底有多少个第一段的前缀和等于sum/3，并记录。当第三段前缀和等于三的时候在result中加入所记录的数据
public class Main_8 {
static final int A = 100010;// 根据数据范围开辟数组长度
static int sum[] = new int[A];
static long result = 0;
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();// 数据个数
for (int i = 1; i <= n; i++) {
sum[i] = sum[i - 1] + scanner.nextInt();// 数组的前缀和
}
if (sum[n] % 3 != 0) {
System.out.println(0);// 如果所有数的和不能整除3，则返回个数0
return;
}
//for循环代表第二道所处位置,要从3处开始，因为要给第一串数组和第二串数组留下至少一个元素
for (int i = 3,cnt = 0; i <= n; i++) {
if(sum[i-2] == (sum[n]/3)) cnt++;
if(sum[n]-sum[i-1]==(sum[n]/3)) result += cnt;
}
System.out.println(result);
scanner.close();
}
}
题目2：
* 输入一个长度为 n 的整数序列。
*
* 接下来再输入 m 个询问，每个询问输入一对 l,r 。
*
* 对于每个询问，输出原序列中从第 l 个数到第 r 个数的和。
*
* 输入格式 第一行包含两个整数 n 和 m 。
*
* 第二行包含 n 个整数，表示整数数列。
*
* 接下来 m 行，每行包含两个整数 l 和 r ，表示一个询问的区间范围。
*
* 输出格式 共 m 行，每行输出一个询问的结果。
*
* 数据范围 1≤l≤r≤n , 1≤n,m≤100000 , −1000≤数列中元素的值≤1000
*
* 输入样例： 5
*
* 3 2 1 3 6 4
*
* 1 2
*
* 1 3
*
* 2 4 输出样例： 3 6 10
public class Main_9 {
static final int N = 100000;
static int[] sum = new int[N];
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int m = scanner.nextInt();
// 直接遍历获得前缀和数组
for (int i = 1; i <= n; i++) {
sum[i] = sum[i - 1] + scanner.nextInt();
}
long[] res = new long[m];
for (int i = 0; i < m; i++) {
int l = scanner.nextInt();
int r = scanner.nextInt();
res[i] = sum[r] - sum[l - 1];
}
for (int i = 0; i < m; i++)
System.out.println(res[i]);
scanner.close();
}
}
双指针
问题1：
* 给定一个长度为 n 的整数序列，请找出最长的不包含重复的数的连续区间，输出它的长度。
*
* 输入格式 第一行包含整数 n 。
*
* 第二行包含 n 个整数（均在 0∼10^5 范围内），表示整数序列。
*
* 输出格式 共一行，包含一个整数，表示最长的不包含重复的数的连续区间的长度。
*
* 数据范围 1≤n≤10^5 输入样例： 5
*
* 1 2 2 3 5 输出样例： 3
public class Main_8 {
static int[] nums = new int[100010];
static int n;
static int res=0;
static int[] temp = new int[100010];
public static void main(String[] args) {
Scanner scanner = new Scanner(new BufferedInputStream(System.in));
n = scanner.nextInt();
for (int i = 0; i < n; i++) {
nums[i] = scanner.nextInt();
}
for(int i=0,j=0;i<n;i++) {
temp[nums[i]]++;
while(j<=i&&temp[nums[i]]>1) {
temp[nums[j]]--;
j++;
}
res=Math.max(res, i-j+1);
}
System.out.println(res);
}
}
