C++实现LeetCode(170.两数之和之三 - 数据结构设计)

[LeetCode] 170. Two Sum III - Data structure design 两数之和之三 - 数据结构设计

Design and implement a TwoSum class. It should support the following operations: add and find.

add - Add the number to an internal data structure.
find - Find if there exists any pair of numbers which sum is equal to the value.

Example 1:

add(1); add(3); add(5);
find(4) -> true
find(7) -> false

Example 2:

add(3); add(1); add(2);
find(3) -> true
find(6) -> false

这道题让我们设计一个 Two Sum 的数据结构，跟 LeetCode 的第一道题 Two Sum 没有什么太大的区别，作为 LeetCode 的首题，Two Sum 的名气不小啊，正所谓平生不会 TwoSum，刷尽 LeetCode 也枉然。记得原来在背单词的时候，总是记得第一个单词是 abandon，结果有些人背来背去还在 abandon，有时候想想刷题其实跟背 GRE 红宝书没啥太大的区别，都是一个熟练功夫，并不需要有多高的天赋，只要下足功夫，都能达到一个很不错的水平，套用一句鸡汤问来激励下吧，“有些时候我们的努力程度根本达不到需要拼天赋的地步”，好了，不闲扯了，来看题吧。不过这题也没啥可讲的，会做 Two Sum 的这题就很简单了，先来看用 HashMap 的解法，把每个数字和其出现的次数建立映射，然后遍历 HashMap，对于每个值，先求出此值和目标值之间的差值t，然后需要分两种情况来看，如果当前值不等于差值t，那么只要 HashMap 中有差值t就返回 True，或者是当差值t等于当前值时，如果此时 HashMap 的映射次数大于1，则表示 HashMap 中还有另一个和当前值相等的数字，二者相加就是目标值，参见代码如下：

解法一：

class TwoSum {
public:
    void add(int number) {
        ++m[number];
    }
    bool find(int value) {
        for (auto a : m) {
            int t = value - a.first;
            if ((t != a.first && m.count(t)) || (t == a.first && a.second > 1)) {
                return true;
            }
        }
        return false;
    }
private:
    unordered_map<int, int> m;
};

另一种解法不用 HashMap，而是 unordered_multiset 来做，但是原理和上面一样，参见代码如下：

解法二：

class TwoSum {
public:
    void add(int number) {
        s.insert(number);
    }
    bool find(int value) {
        for (auto a : s) {
            int cnt = a == value - a ? 1 : 0;
            if (s.count(value - a) > cnt) {
                return true;
            }
        }
        return false;
    }
private:
    unordered_multiset<int> s;
};

Github 同步地址：

https://github.com/grandyang/leetcode/issues/170

类似题目：

Two Sum

Unique Word Abbreviation

Two Sum IV - Input is a BST

参考资料：

https://leetcode.com/problems/two-sum-iii-data-structure-design/

https://leetcode.com/problems/two-sum-iii-data-structure-design/discuss/52015/Beats-100-Java-Code

https://leetcode.com/problems/two-sum-iii-data-structure-design/discuss/52035/My-solutions-in-Java-C%2B%2B-and-Python.-O(1)-time-for-add-O(n)-time-for-find-O(n)-space

到此这篇关于C++实现LeetCode(170.两数之和之三 - 数据结构设计)的文章就介绍到这了,更多相关C++实现两数之和之三 - 数据结构设计内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！

赞 (0)

相关推荐

  • C++实现LeetCode(171.求Excel表列序号)

    [LeetCode] 171.Excel Sheet Column Number 求Excel表列序号 Related to question Excel Sheet Column Title Given a column title as appear in an Excel sheet, return its corresponding column number. For example:     A -> 1 B -> 2 C -> 3 ... Z -> 26 AA -&g

  • C++实现LeetCode(166.分数转循环小数)

    [LeetCode] 166.Fraction to Recurring Decimal 分数转循环小数 Given two integers representing the numerator and denominator of a fraction, return the fraction in string format. If the fractional part is repeating, enclose the repeating part in parentheses. Fo

  • C++实现LeetCode(169.求大多数)

    [LeetCode] 169. Majority Element 求大多数 Given an array nums of size n, return the majority element. The majority element is the element that appears more than ⌊n / 2⌋ times. You may assume that the majority element always exists in the array. Example 1

  • C++实现LeetCode(164.求最大间距)

    [LeetCode] 164. Maximum Gap 求最大间距 Given an unsorted array, find the maximum difference between the successive elements in its sorted form. Return 0 if the array contains less than 2 elements. Example 1: Input: [3,6,9,1] Output: 3 Explanation: The sor

  • C++实现LeetCode(168.求Excel表列名称)

    [LeetCode] 168.Excel Sheet Column Title 求Excel表列名称 Given a positive integer, return its corresponding column title as appear in an Excel sheet. For example:     1 -> A 2 -> B 3 -> C ... 26 -> Z 27 -> AA 28 -> AB ... Example 1: Input: 1 O

  • C++实现LeetCode(228.总结区间)

    [LeetCode] 228.Summary Ranges 总结区间 Given a sorted integer array without duplicates, return the summary of its ranges. Example 1: Input:  [0,1,2,4,5,7] Output: ["0->2","4->5","7"] Explanation: 0,1,2 form a continuous ran

  • C++实现LeetCode165.版本比较)

    [LeetCode] 165.Compare Version Numbers 版本比较 Compare two version numbers version1 and version2. If version1 > version2 return 1; if version1 <version2 return -1;otherwise return 0. You may assume that the version strings are non-empty and contain onl

  • C++实现LeetCode(167.两数之和之二 - 输入数组有序)

    [LeetCode] 167.Two Sum II - Input array is sorted 两数之和之二 - 输入数组有序 Given an array of integers that is already sorted in ascending order, find two numbers such that they add up to a specific target number. The function twoSum should return indices of t

  • C++实现LeetCode(170.两数之和之三 - 数据结构设计)

    [LeetCode] 170. Two Sum III - Data structure design 两数之和之三 - 数据结构设计 Design and implement a TwoSum class. It should support the following operations: add and find. add - Add the number to an internal data structure. find - Find if there exists any pai

  • Java实现LeetCode（两数之和）

    给定一个整数数组和一个目标值,找出数组中和为目标值的两个数. 你可以假设每个输入只对应一种答案,且同样的元素不能被重复利用. 示例: 给定 nums = [2, 7, 11, 15], target = 9 因为 nums[0] + nums[1] = 2 + 7 = 9 所以返回[0, 1] 思路一:最直接的思维,两次遍历查询,时间复杂度O(N*N). 代码: public static int[] twoSum1(int[] nums, int target) { int[] label =

  • C++实现LeetCode（三数之和）

    Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero. Note: Elements in a triplet (a,b,c) must be in non-descending order. (ie, a ≤ b ≤ c) The solut

  • C++实现LeetCode(18.四数之和)

    [LeetCode] 18. 4Sum 四数之和 Given an array S of n integers, are there elements a, b, c, and d in S such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target. Note: Elements in a quadruplet (a,b,c,d) must be

  • JS求解两数之和算法详解

    本文实例讲述了JS求解两数之和算法.分享给大家供大家参考,具体如下: 题目描述 给定一个整数数组和一个目标值,找出数组中和为目标值的两个数. 你可以假设每个输入只对应一种答案,且同样的元素不能被重复利用. ::: tip 给定 nums = [2, 7, 11, 15], target = 9 因为 nums[0] + nums[1] = 2 + 7 = 9 所以返回 [0, 1] ::: 解法 利用 Map 记录数组元素值和对应的下标,对于一个数 nums[i],判断 target - num

  • C++实现LeetCode(29.两数相除)

    [LeetCode] 29. Divide Two Integers 两数相除 Given two integers dividend and divisor, divide two integers without using multiplication, division and mod operator. Return the quotient after dividing dividend by divisor. The integer division should truncate

  • 使用python实现两数之和的画解算法

    使用python实现两数之和的画解算法

    题目描述 给定一个整数数组 nums 和一个整数目标值 target,请你在该数组中找出 和为目标值 target 的那 两个 整数,并返回它们的数组下标. 你可以假设每种输入只会对应一个答案.但是,数组中同一个元素在答案里不能重复出现. 你可以按任意顺序返回答案. 示例 1: 输入:nums = [2,7,11,15], target = 9 输出:[0,1] 解释:因为 nums[0] + nums[1] == 9 ,返回 [0, 1] . 示例 2: 输入:nums = [3,2,4],

  • c语言如何实现两数之和

    c语言如何实现两数之和

    目录 c语言实现两数之和 c语言中比较两数大小 题目要求 分析一下 c语言实现两数之和 int *twoSum(int *nums , int numsSize , int target , int *returnSize) { int i = 0 , j = 0; *returnSize = 2; int *a = (int *)malloc(sizeof(int) * 2); for(i = 0;i<numsSize;i++) { for(j=i+1;j<numsSize;j++) { i

  • C++实现LeetCode(211.添加和查找单词-数据结构设计)

    [LeetCode] 211.Add and Search Word - Data structure design 添加和查找单词-数据结构设计 Design a data structure that supports the following two operations: void addWord(word) bool search(word) search(word) can search a literal word or a regular expression string c

随机推荐