Java实现 LeetCode 446 等差数列划分 II - 子序列
2023-09-14 08:58:05 时间
446. 等差数列划分 II - 子序列
如果一个数列至少有三个元素,并且任意两个相邻元素之差相同,则称该数列为等差数列。
例如,以下数列为等差数列:
1, 3, 5, 7, 9
7, 7, 7, 7
3, -1, -5, -9
以下数列不是等差数列。
1, 1, 2, 5, 7
数组 A 包含 N 个数,且索引从 0 开始。该数组子序列将划分为整数序列 (P0, P1, …, Pk),P 与 Q 是整数且满足 0 ≤ P0 < P1 < … < Pk < N。
如果序列 A[P0],A[P1],…,A[Pk-1],A[Pk] 是等差的,那么数组 A 的子序列 (P0,P1,…,PK) 称为等差序列。值得注意的是,这意味着 k ≥ 2。
函数要返回数组 A 中所有等差子序列的个数。
输入包含 N 个整数。每个整数都在 -231 和 231-1 之间,另外 0 ≤ N ≤ 1000。保证输出小于 231-1。
示例:
输入:[2, 4, 6, 8, 10]
输出:7
解释:
所有的等差子序列为:
[2,4,6]
[4,6,8]
[6,8,10]
[2,4,6,8]
[4,6,8,10]
[2,4,6,8,10]
[2,6,10]
PS:
等差数列,差相等,我for循环,把差当作map的key,数量当作value,然后暴力大法
class Solution {
public int numberOfArithmeticSlices(int[] A) {
int n = A.length;
long ans = 0;
Map<Integer, Integer>[] cnt = new Map[n];
for (int i = 0; i < n; i++) {
cnt[i] = new HashMap<>(i);
for (int j = 0; j < i; j++) {
long delta = (long)A[i] - (long)A[j];
if (delta < Integer.MIN_VALUE || delta > Integer.MAX_VALUE) {
continue;
}
int diff = (int)delta;
int sum = cnt[j].getOrDefault(diff, 0);
int origin = cnt[i].getOrDefault(diff, 0);
cnt[i].put(diff, origin + sum + 1);
ans += sum;
}
}
return (int)ans;
}
}
相关文章
- JAVA三元运算符_java中三元运算符详解
- Java递归下降分析器_递归下降语法分析器[通俗易懂]
- java是面向对象还是面向过程_Java面向对象编程和面向过程编程的区别[通俗易懂]
- Cookie–记住上一次访问时间案例(Java)
- java messagedigest_Java 自带的加密类MessageDigest类(加密MD5和SHA)[通俗易懂]
- java extends runtimeexception_Java中RuntimeException和Exception的区别
- MySQL字段类型如何转为java_Java JDBC中,MySQL字段类型到JAVA类型的转换
- java uuid 随机数_Java随机数和UUID[通俗易懂]
- java 调用bapi_BAPI的简单实现步骤
- 微信开发SDK java版,支持maven;微信Java开发工具包,支持包括微信支付、开放平台、公众号、企业微信/企业号、小程序等微信功能模块的后端开发。
- Hudi Java Client总结|读取Hive写Hudi代码示例
- Java易错知识点总结(二)
- JAVA读取csv文件_java读取csv文件某一列
- 贼 TM 好用的 Java 工具类库
- 【错误记录】Java AWT 图形界面编程报错 ( Exception in thread “main“ java.awt.AWTError: BoxLayout can‘t be shared )
- java实现Excel导入导出功能
- ORA-29532: Java call terminated by uncaught Java exception: string ORACLE 报错 故障修复 远程处理
- java如何读取txt文件内容详解编程语言
- java使用Post和Get方式提交Http请求通用详解编程语言
- 代码Linux下编写Java代码的指南(linux编写java)
- Control character in cookie value, consider BASE64 encoding your value , java操作cookie遇到中文会报错的解决方案详解编程语言
- Java 多线程详解编程语言
- 更新LINUX下的Java版本(linux更新java)
- 处理Java处理Redis的过期策略(redisjava过期)
- 国内首本系统讲解Java异步编程的书籍-java异步编程实战
- Java调用Linux库实现跨系统功能(java调用linux库)
- 如何使用Java备份Oracle数据库?(java备份oracle)
- 数据Java操作MySQL库:获取你所需的数据(java获取mysql)
- Java桥接Oracle让数据轻松流动(java桥接oracle)
- java与c#的语法区别详细介绍