1 Star 0 Fork 332

傍地走 / leetcode

forked from doocs / leetcode 
加入 Gitee
与超过 1200万 开发者一起发现、参与优秀开源项目,私有仓库也完全免费 :)
免费加入
克隆/下载
README.md 4.81 KB
一键复制 编辑 原始数据 按行查看 历史
ylb 提交于 2022-08-13 22:42 . style: format all python code

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

English Version

题目描述

给你两个整数数组 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) 数目。

 

示例:

,5,4

 

提示:

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

解法

“哈希表”实现。

Python3

class FindSumPairs:
    def __init__(self, nums1: List[int], nums2: List[int]):
        self.nums1 = nums1
        self.nums2 = nums2
        self.counter = Counter(nums2)

    def add(self, index: int, val: int) -> None:
        old_val = self.nums2[index]
        self.counter[old_val] -= 1
        self.nums2[index] += val
        self.counter[old_val + val] += 1

    def count(self, tot: int) -> int:
        return sum([self.counter[tot - num] for num in self.nums1])


# Your FindSumPairs object will be instantiated and called as such:
# obj = FindSumPairs(nums1, nums2)
# obj.add(index,val)
# param_2 = obj.count(tot)

Java

class FindSumPairs {
    private int[] nums1;
    private int[] nums2;
    private Map<Integer, Integer> counter;

    public FindSumPairs(int[] nums1, int[] nums2) {
        this.nums1 = nums1;
        this.nums2 = nums2;
        counter = new HashMap<>();
        for (int num : nums2) {
            counter.put(num, counter.getOrDefault(num, 0) + 1);
        }
    }

    public void add(int index, int val) {
        int oldVal = nums2[index];
        counter.put(oldVal, counter.get(oldVal) - 1);
        nums2[index] += val;
        counter.put(oldVal + val, counter.getOrDefault(oldVal + val, 0) + 1);
    }

    public int count(int tot) {
        int res = 0;
        for (int num : nums1) {
            res += counter.getOrDefault(tot - num, 0);
        }
        return res;
    }
}

/**
 * Your FindSumPairs object will be instantiated and called as such:
 * FindSumPairs obj = new FindSumPairs(nums1, nums2);
 * obj.add(index,val);
 * int param_2 = obj.count(tot);
 */

...

马建仓 AI 助手
尝试更多
代码解读
代码找茬
代码优化
Java
1
https://gitee.com/noodlesAI/leetcode.git
git@gitee.com:noodlesAI/leetcode.git
noodlesAI
leetcode
leetcode
main

搜索帮助

344bd9b3 5694891 D2dac590 5694891