1865. Finding Pairs With a Certain Sum Medium

1/**
2 * [1865] Finding Pairs With a Certain Sum
3 *
4 * You are given two integer arrays nums1 and nums2. You are tasked to implement a data structure that supports queries of two types:
5 * <ol>
6 * 	Add a positive integer to an element of a given index in the array nums2.
7 * 	Count the number of pairs (i, j) such that nums1[i] + nums2[j] equals a given value (0 <= i < nums1.length and 0 <= j < nums2.length).
8 * </ol>
9 * Implement the FindSumPairs class:
10 * 
11 * 	FindSumPairs(int[] nums1, int[] nums2) Initializes the FindSumPairs object with two integer arrays nums1 and nums2.
12 * 	void add(int index, int val) Adds val to nums2[index], i.e., apply nums2[index] += val.
13 * 	int count(int tot) Returns the number of pairs (i, j) such that nums1[i] + nums2[j] == tot.
14 * 
15 *  
16 * Example 1:
17 * 
18 * Input
19 * ["FindSumPairs", "count", "add", "count", "count", "add", "add", "count"]
20 * [[[1, 1, 2, 2, 2, 3], [1, 4, 5, 2, 5, 4]], [7], [3, 2], [8], [4], [0, 1], [1, 1], [7]]
21 * Output
22 * [null, 8, null, 2, 1, null, null, 11]
23 * Explanation
24 * FindSumPairs findSumPairs = new FindSumPairs([1, 1, 2, 2, 2, 3], [1, 4, 5, 2, 5, 4]);
25 * findSumPairs.count(7);  // return 8; pairs (2,2), (3,2), (4,2), (2,4), (3,4), (4,4) make 2 + 5 and pairs (5,1), (5,5) make 3 + 4
26 * findSumPairs.add(3, 2); // now nums2 = [1,4,5,<u>4</u>,5,4]
27 * findSumPairs.count(8);  // return 2; pairs (5,2), (5,4) make 3 + 5
28 * findSumPairs.count(4);  // return 1; pair (5,0) makes 3 + 1
29 * findSumPairs.add(0, 1); // now nums2 = [<u>2</u>,4,5,4,5,4]
30 * findSumPairs.add(1, 1); // now nums2 = [2,<u>5</u>,5,4,5,4]
31 * findSumPairs.count(7);  // return 11; pairs (2,1), (2,2), (2,4), (3,1), (3,2), (3,4), (4,1), (4,2), (4,4) make 2 + 5 and pairs (5,3), (5,5) make 3 + 4
32 * 
33 *  
34 * Constraints:
35 * 
36 * 	1 <= nums1.length <= 1000
37 * 	1 <= nums2.length <= 10^5
38 * 	1 <= nums1[i] <= 10^9
39 * 	1 <= nums2[i] <= 10^5
40 * 	0 <= index < nums2.length
41 * 	1 <= val <= 10^5
42 * 	1 <= tot <= 10^9
43 * 	At most 1000 calls are made to add and count each.
44 * 
45 */
46pub struct Solution {}
47
48// problem: https://leetcode.com/problems/finding-pairs-with-a-certain-sum/
49// discuss: https://leetcode.com/problems/finding-pairs-with-a-certain-sum/discuss/?currentPage=1&orderBy=most_votes&query=
50
51// submission codes start here
52
53struct FindSumPairs {
54        false
55    }
56
57
58/** 
59 * `&self` means the method takes an immutable reference.
60 * If you need a mutable reference, change it to `&mut self` instead.
61 */
62impl FindSumPairs {
63
64    fn new(nums1: Vec<i32>, nums2: Vec<i32>) -> Self {
65        
66    }
67    
68    fn add(&self, index: i32, val: i32) {
69        
70    }
71    
72    fn count(&self, tot: i32) -> i32 {
73        
74    }
75}
76
77/**
78 * Your FindSumPairs object will be instantiated and called as such:
79 * let obj = FindSumPairs::new(nums1, nums2);
80 * obj.add(index, val);
81 * let ret_2: i32 = obj.count(tot);
82 */
83
84// submission codes end
85
86#[cfg(test)]
87mod tests {
88    use super::*;
89
90    #[test]
91    fn test_1865() {
92    }
93}
94