LeetCode 170. 两数之和 III - 数据结构设计

Categories:

题目描述
思路分析
1. 解法一：哈希表（推荐）
2. 解法二：有序列表 + 双指针
相似题目

题目描述

✅ 170. 两数之和 III - 数据结构设计

思路分析

解法一：哈希表（推荐）

核心思路：

使用 HashMap 记录每个数字出现的次数（支持重复数字）

add(number) 操作直接将数字加入哈希表，计数 +1

find(value) 操作枚举哈希表中每个 key，判断 value - key 是否存在

对于 value - key == key 的情况，需要该数字出现次数 >= 2

空间换时间，add 为 O(1)，find 为 O(n)

复杂度分析：

时间复杂度：add O(1)，find O(n)，其中 n 为已添加的数字个数

空间复杂度：O(n)，哈希表存储所有已添加的数字

class TwoSum {

    private Map<Integer, Integer> countMap;

    public TwoSum() {
        countMap = new HashMap<>();
    }

    public void add(int number) {
        // 记录每个数字出现次数
        countMap.put(number, countMap.getOrDefault(number, 0) + 1);
    }

    public boolean find(int value) {
        for (Map.Entry<Integer, Integer> entry : countMap.entrySet()) {
            int num = entry.getKey();
            int complement = value - num;

            if (complement == num) {
                // 两个相同的数，需要出现至少两次
                if (entry.getValue() >= 2) {
                    return true;
                }
            } else {
                // 两个不同的数，complement 存在即可
                if (countMap.containsKey(complement)) {
                    return true;
                }
            }
        }
        return false;
    }
}

type TwoSum struct {
    countMap map[int]int
}

func Constructor() TwoSum {
    return TwoSum{countMap: make(map[int]int)}
}

func (t *TwoSum) Add(number int) {
    // 记录每个数字出现次数
    t.countMap[number]++
}

func (t *TwoSum) Find(value int) bool {
    for num, cnt := range t.countMap {
        complement := value - num

        if complement == num {
            // 两个相同的数，需要出现至少两次
            if cnt >= 2 {
                return true
            }
        } else {
            // 两个不同的数，complement 存在即可
            if _, ok := t.countMap[complement]; ok {
                return true
            }
        }
    }
    return false
}

解法二：有序列表 + 双指针

核心思路：

用 List 存储所有数字，add 时将数字加入列表

find 时先对列表排序，再用双指针从两端向中间逼近

适合 add 频率低、find 频率高的场景

若 add 多 find 少，则每次 find 排序代价较高

复杂度分析：

时间复杂度：add O(1)，find O(n log n)，其中 n 为已添加的数字个数

空间复杂度：O(n)，列表存储所有数字

class TwoSum {

    private List<Integer> nums;

    public TwoSum() {
        nums = new ArrayList<>();
    }

    public void add(int number) {
        nums.add(number);
    }

    public boolean find(int value) {
        Collections.sort(nums);

        int left = 0;
        int right = nums.size() - 1;

        while (left < right) {
            int sum = nums.get(left) + nums.get(right);

            if (sum == value) {
                return true;
            } else if (sum < value) {
                left++;
            } else {
                right--;
            }
        }
        return false;
    }
}

import "sort"

type TwoSum struct {
    nums []int
}

func Constructor() TwoSum {
    return TwoSum{}
}

func (t *TwoSum) Add(number int) {
    t.nums = append(t.nums, number)
}

func (t *TwoSum) Find(value int) bool {
    sorted := make([]int, len(t.nums))
    copy(sorted, t.nums)
    sort.Ints(sorted)

    left, right := 0, len(sorted)-1

    for left < right {
        sum := sorted[left] + sorted[right]

        if sum == value {
            return true
        } else if sum < value {
            left++
        } else {
            right--
        }
    }
    return false
}

相似题目

题目	难度	考察点
1. 两数之和	简单	哈希表
167. 两数之和 II - 输入有序数组	中等	双指针
653. 两数之和 IV - 输入二叉搜索树	简单	哈希表、二叉树
15. 三数之和	中等	双指针、排序
18. 四数之和	中等	双指针、排序
560. 和为 K 的子数组	中等	哈希表、前缀和

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2023/74855848