当前位置: 首页 > news >正文

leetcode 每日一题 1865. 找出和为指定值的下标对

1865. 找出和为指定值的下标对

给你两个整数数组 nums1nums2 ,请你实现一个支持下述两类查询的数据结构:

  1. 累加 ,将一个正整数加到 nums2 中指定下标对应元素上。
  2. 计数 ,统计满足 nums1[i] + nums2[j] 等于指定值的下标对 (i, j) 数目(0 <= i < nums1.length0 <= j < nums2.length)。
    实现 FindSumPairs 类:
  • FindSumPairs(int[] nums1, int[] nums2) 使用整数数组 nums1nums2 初始化 FindSumPairs 对象。
  • void add(int index, int val)val 加到 nums2[index] 上,即,执行 nums2[index] += val
  • int count(int tot) 返回满足 nums1[i] + nums2[j] == tot 的下标对 (i, j) 数目。
    示例:
    输入:
["FindSumPairs", "count", "add", "count", "count", "add", "add", "count"]
[[[1, 1, 2, 2, 2, 3], [1, 4, 5, 2, 5, 4]], [7], [3, 2], [8], [4], [0, 1], [1, 1], [7]]

输出:

[null, 8, null, 2, 1, null, null, 11]

解释:
FindSumPairs findSumPairs = new FindSumPairs([1, 1, 2, 2, 2, 3], [1, 4, 5, 2, 5, 4]);
findSumPairs.count(7); // 返回 8 ; 下标对 (2,2), (3,2), (4,2), (2,4), (3,4), (4,4) 满足 2 + 5 = 7 ,下标对 (5,1), (5,5) 满足 3 + 4 = 7
findSumPairs.add(3, 2); // 此时 nums2 = [1,4,5,4,5,4]
findSumPairs.count(8); // 返回 2 ;下标对 (5,2), (5,4) 满足 3 + 5 = 8
findSumPairs.count(4); // 返回 1 ;下标对 (5,0) 满足 3 + 1 = 4
findSumPairs.add(0, 1); // 此时 nums2 = [2,4,5,4,5,4]
findSumPairs.add(1, 1); // 此时 nums2 = [2,5,5,4,5,4]
findSumPairs.count(7); // 返回 11 ;下标对 (2,1), (2,2), (2,4), (3,1), (3,2), (3,4), (4,1), (4,2), (4,4) 满足 2 + 5 = 7 ,下标对 (5,3), (5,5) 满足 3 + 4 = 7
提示:

  • 1 <= nums1.length <= 1000
  • 1 <= nums2.length <= 10^5
  • 1 <= nums1[i] <= 10^9
  • 1 <= nums2[i] <= 10^5
  • 0 <= index < nums2.length
  • 1 <= val <= 10^5
  • 1 <= tot <= 10^9
  • 最多调用 addcount 函数各 1000

思路

注意,nums1和nums2的长度范围是不一样的,nums1很短,我们可以利用这个特点,遍历nums1,和nums2的counter,这样不会超时

type FindSumPairs struct {  nums1 []int       // nums1.length <= 1000  nums2 []int       // nums2.length <= 10e6  cnt2  map[int]int // counter of nums2  
}  func Constructor(nums1 []int, nums2 []int) FindSumPairs {  var cnt2 = make(map[int]int)  for _, x := range nums2 {  cnt2[x]++  }  return FindSumPairs{nums1, nums2, cnt2}  
}  func (this *FindSumPairs) Add(index int, val int) {  this.cnt2[this.nums2[index]]--  this.nums2[index] += val  this.cnt2[this.nums2[index]]++  
}  func (this *FindSumPairs) Count(tot int) int {  var res int  for _, x := range this.nums1 {  res += this.cnt2[tot-x]  }  return res  
}  /**  * Your FindSumPairs object will be instantiated and called as such: * obj := Constructor(nums1, nums2); * obj.Add(index,val); * param_2 := obj.Count(tot); */

也可以把nums1和nums2都转为counter

type FindSumPairs struct {  nums1 []int       // nums1.length <= 1000  nums2 []int       // nums2.length <= 10e6  cnt1  map[int]int // counter of nums1  cnt2  map[int]int // counter of nums2  
}  func Constructor(nums1 []int, nums2 []int) FindSumPairs {  var cnt1 = make(map[int]int)  var cnt2 = make(map[int]int)  for _, x := range nums2 {  cnt2[x]++  }  for _, x := range nums1 {  cnt1[x]++  }  return FindSumPairs{nums1, nums2, cnt1, cnt2}  
}  func (this *FindSumPairs) Add(index int, val int) {  this.cnt2[this.nums2[index]]--  this.nums2[index] += val  this.cnt2[this.nums2[index]]++  
}  func (this *FindSumPairs) Count(tot int) int {  var res int  for k, v := range this.cnt1 {  res += v * (this.cnt2[tot-k])  }  return res  
}
http://www.xdnf.cn/news/1083277.html

相关文章:

  • uniapp实现的多种时间线模板
  • Redis存储Cookie实现爬虫保持登录 requests | selenium
  • TCP/IP协议栈实现浅析(下) 报文接收相关函数及流程分析
  • 软件版本FCCU(故障采集与控制单元)设计
  • RS触发器Multisim电路仿真——硬件工程师笔记
  • Linux命令大全:按功能分类详解(附表格速查)
  • Altium Designer使用教程 第一章(Altium Designer工程与窗口)
  • 用户中心Vue3网页开发(1.0版)
  • Attention Is All You Need论文精读(逐段解析)
  • 隐马尔可夫模型:语音识别系统的时序解码引擎
  • python优先队列使用
  • H3C WA6322 Fit AP切换为云AP或Anchor-AC(FAT AP)
  • 如何理解lambda排序
  • 自动化Prompt生成平台的研发体系设计
  • 《Redis》哨兵模式
  • 数据结构——栈的讲解(超详细)
  • python使用fastmcp包编写mcp服务端(mcp_server)和mcp客户端(mcp_client)
  • Java教程——深入学习guava之并发编程
  • 如何使用backtrace定位Linux程序的崩溃位置
  • 大数据学习2:HIve
  • 故障诊断 | CNN-GRU-Attention故障诊断
  • LINUX75 LAMP
  • 前端-CSS-day1
  • Softhub软件下载站实战开发(十三):软件管理前端分片上传实现
  • 从零构建智能ai语音助手:ESP32s3+Python+大语言模型实战指南
  • SQL128 统计2021年未完成试卷作答数大于1的有效用户
  • Linux操作系统之文件(四):文件系统(上)
  • Android PNG/JPG图ARGB_8888/RGB_565‌解码形成Bitmap在物理内存占用大小的简单计算
  • STM32中实现shell控制台(命令解析实现)
  • [Cyclone] 哈希算法 | SIMD优化哈希计算 | 大数运算 (Int类)