两数之和 III-数据结构设计

zzzrf：设计并实现一个 TwoSum 类。他需要支持以下操作:add 和 find 。

add -把这个数添加到内部的数据结构。
find -是否存在任意一对数字之和等于这个值

点此在线做题

样例 1:

add(1);add(3);add(5);
find(4)//返回 true
find(7)//返回 false

[题解]

使用哈希表的方法是最快的。

• add 可以做到 O(1)
• find 可以做到 O(n)

public class TwoSum {
    private Map<Integer, Integer> counter;
    
    public TwoSum() {
        counter = new HashMap<Integer, Integer>();
    }

    // Add the number to an internal data structure.
    public void add(int number) {
        counter.put(number, counter.getOrDefault(number, 0) + 1);
    }

    // Find if there exists any pair of numbers which sum is equal to the value.
    public boolean find(int value) {
        for (Integer num1 : counter.keySet()) {
            int num2 = value - num1;
            int desiredCount = num1 == num2 ? 2 : 1;
            if (counter.getOrDefault(num2, 0) >= desiredCount) {
                return true;
            }
        }
        return false;
    }
}
// Your TwoSum object will be instantiated and called as such:// TwoSum twoSum = new TwoSum();// twoSum.add(number);// twoSum.find(value);

排序数组+双指针的算法会超时，但是大家可以看看是怎么写的，时间复杂度：
- add O(n)
- find O(n)

public class TwoSum {
    public List<Integer> nums;
    public TwoSum() {
        nums = new ArrayList<Integer>();
    }
    
    public void add(int number) {
        nums.add(number);
        int index = nums.size() - 1;
        while (index > 0 && nums.get(index - 1) > nums.get(index)) {
            int temp = nums.get(index);
            nums.set(index, nums.get(index - 1));
            nums.set(index - 1, temp);
            index--;
        }
    }

    public boolean find(int value) {
        int left = 0, right = nums.size() - 1;
        while (left < right) {
            int twoSum = nums.get(left) + nums.get(right);
            if (twoSum < value) {
                left++;
            } else if (twoSum > value) {
                right--;
            } else {
                return true;
            }
        }
        return false;
    }
}

查看更多题解

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…

脑子突然不好使了，请各位大佬帮我想想这个算法

lihongming：已知有一个长度为 26 的整型数组，分别代表 26 个字母的个数，问这些字母能组成多少种不同的字符串（取模 1000000007 ）。 我本来觉得挺简单，不就是迭代吗？抬手就来 int calc(int[] nums) { int ret = 0; for (int i = 0; i < nums.length; i++) { i…

备案期间域名能解析境外吗

zok2002：备案期间域名能解析境外吗，境内不解析

LeetCode题解1201. 丑数 III

请你帮忙设计一个程序，用来找出第 n 个丑数。丑数是可以被 a 或 b 或 c 整除的 正整数。 示例 1：输入：n = 3, a = 2, b = 3, c = 5输出：4解释：丑数序列为 2, 3, 4, 5, 6, 8, 9, 10... 其中第 3 个是 4。示例 2：输入：n = 4, a = 2, b = 3, c = 4输出：6解释：丑数序列为…

LeetCode题解437.path-sum-iii

题目地址 https://leetcode.com/problems/path-sum-iii/description/ 题目描述 You are given a binary tree in which each node contains an integer value. Find the number of paths that sum to a g…