洛谷 P1102 A-B 数对 (Java)

2024-02-14 01:12
文章标签 java 洛谷 数对 p1102

本文主要是介绍洛谷 P1102 A-B 数对 (Java),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

洛谷 P1102 A-B 数对 (Java)

传送门:P1102 A-B 数对

题目: A-B 数对

题目背景

出题是一件痛苦的事情!

相同的题目看多了也会有审美疲劳,于是我舍弃了大家所熟悉的 A+B Problem,改用 A-B 了哈哈!

题目描述

给出一串正整数数列以及一个正整数 C C C,要求计算出所有满足 A − B = C A - B = C AB=C 的数对的个数(不同位置的数字一样的数对算不同的数对)。

输入格式

输入共两行。

第一行,两个正整数 N , C N,C N,C

第二行, N N N 个正整数,作为要求处理的那串数。

输出格式

一行,表示该串正整数中包含的满足 A − B = C A - B = C AB=C 的数对的个数。

样例 #1

样例输入 #1

4 1
1 1 2 3

样例输出 #1

3

提示

对于 75 % 75\% 75% 的数据, 1 ≤ N ≤ 2000 1 \leq N \leq 2000 1N2000

对于 100 % 100\% 100% 的数据, 1 ≤ N ≤ 2 × 1 0 5 1 \leq N \leq 2 \times 10^5 1N2×105 0 ≤ a i < 2 30 0 \leq a_i <2^{30} 0ai<230 1 ≤ C < 2 30 1 \leq C < 2^{30} 1C<230

2017/4/29 新添数据两组

分析:

创建一个 HashMap map,用于记录数组中每个数字的出现次数。

创建一个数组 a,用于存储输入的整数数组。

定义cnt 用于记录满足条件的数对个数。

再次循环数组 a,对于每个元素 a[i]:

如果 HashMap 中存在键值为 a[i]+c 的项,则将其值加到 cnt 中。
输出 cnt,即为满足条件的数对个数。

这个算法的时间复杂度为 O(N),其中 N 为数组长度。因为在第一个循环中构建了 HashMap,而在第二个循环中通过查找 HashMap 进行计数,每个查找操作的时间复杂度是 O(1)。因此总体的时间复杂度取决于循环次数,即 O(N)。

代码:

import java.util.*;public class Main{public static void main(String[] args) {     Scanner sc = new Scanner(System.in);int n = sc.nextInt();int c = sc.nextInt();Map<Integer,Integer> map = new HashMap<>();int [] a = new int [n];for(int i = 0;i < n;i++) {int tt = sc.nextInt();a[i] = tt;map.compute(tt, (key, value) -> (value == null) ? 1 : value + 1);}long cnt = 0;for(int i = 0;i < n;i++) {if(map.containsKey(a[i]+c)) {cnt += map.get(a[i]+c);}}System.out.println(cnt);sc.close();}
}

这篇关于洛谷 P1102 A-B 数对 (Java)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/707127

相关文章

Java如何根据word模板导出数据

《Java如何根据word模板导出数据》这篇文章主要为大家详细介绍了Java如何实现根据word模板导出数据,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... pom.XML文件导入依赖 <dependency> <groupId>cn.afterturn</groupId>

Java应用如何防止恶意文件上传

《Java应用如何防止恶意文件上传》恶意文件上传可能导致服务器被入侵,数据泄露甚至服务瘫痪,因此我们必须采取全面且有效的防范措施来保护Java应用的安全,下面我们就来看看具体的实现方法吧... 目录恶意文件上传的潜在风险常见的恶意文件上传手段防范恶意文件上传的关键策略严格验证文件类型检查文件内容控制文件存储

浅析Java如何保护敏感数据

《浅析Java如何保护敏感数据》在当今数字化时代,数据安全成为了软件开发中至关重要的课题,本文将深入探讨Java安全领域,聚焦于敏感数据保护的策略与实践,感兴趣的小伙伴可以了解下... 目录一、Java 安全的重要性二、敏感数据加密技术(一)对称加密(二)非对称加密三、敏感数据的访问控制(一)基于角色的访问

Java计算经纬度距离的示例代码

《Java计算经纬度距离的示例代码》在Java中计算两个经纬度之间的距离,可以使用多种方法(代码示例均返回米为单位),文中整理了常用的5种方法,感兴趣的小伙伴可以了解一下... 目录1. Haversine公式(中等精度,推荐通用场景)2. 球面余弦定理(简单但精度较低)3. Vincenty公式(高精度,

使用Java将实体类转换为JSON并输出到控制台的完整过程

《使用Java将实体类转换为JSON并输出到控制台的完整过程》在软件开发的过程中,Java是一种广泛使用的编程语言,而在众多应用中,数据的传输和存储经常需要使用JSON格式,用Java将实体类转换为J... 在软件开发的过程中,Java是一种广泛使用的编程语言,而在众多应用中,数据的传输和存储经常需要使用j

Java实现视频格式转换的完整指南

《Java实现视频格式转换的完整指南》在Java中实现视频格式的转换,通常需要借助第三方工具或库,因为视频的编解码操作复杂且性能需求较高,以下是实现视频格式转换的常用方法和步骤,需要的朋友可以参考下... 目录核心思路方法一:通过调用 FFmpeg 命令步骤示例代码说明优点方法二:使用 Jaffree(FF

Java实现图片淡入淡出效果

《Java实现图片淡入淡出效果》在现代图形用户界面和游戏开发中,**图片淡入淡出(FadeIn/Out)**是一种常见且实用的视觉过渡效果,它可以用于启动画面、场景切换、轮播图、提示框弹出等场景,通过... 目录1. 项目背景详细介绍2. 项目需求详细介绍2.1 功能需求2.2 非功能需求3. 相关技术详细

Java如何用乘号来重复字符串的功能

《Java如何用乘号来重复字符串的功能》:本文主要介绍Java使用乘号来重复字符串的功能,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录Java乘号来重复字符串的功能1、利用循环2、使用StringBuilder3、采用 Java 11 引入的String.rep

SpringBoot中HTTP连接池的配置与优化

《SpringBoot中HTTP连接池的配置与优化》这篇文章主要为大家详细介绍了SpringBoot中HTTP连接池的配置与优化的相关知识,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一... 目录一、HTTP连接池的核心价值二、Spring Boot集成方案方案1:Apache HttpCl

Spring Boot项目打包和运行的操作方法

《SpringBoot项目打包和运行的操作方法》SpringBoot应用内嵌了Web服务器,所以基于SpringBoot开发的web应用也可以独立运行,无须部署到其他Web服务器中,下面以打包dem... 目录一、打包为JAR包并运行1.打包为可执行的 JAR 包2.运行 JAR 包二、打包为WAR包并运行