摘要: 哈希表、双指针

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

各位好，今天我们来看 leetcode 的第一题，这题应该所有人都做过吧，本文我们写一下这一题，算是经典回顾。然后谈一下哈希表解决问题的特点，以后我们再展开哈希表这一主题。

整体的思维过程是这样的，要在集合中查找某个元素，最暴力的方式是直接枚举所有集合元素，然后考虑能不能通过数据结构来维护这个查找操作，再根据需求和数据的特点，定下哈希表这个数据结构。

题目

• 1. 两数之和

给定一个整数数组 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], target = 6
输出：[1,2]

示例 3：
输入：nums = [3,3], target = 6
输出：[0,1]

提示：

1
2
3
4

2 <= nums.length <= 1e4
-1e9 <= nums[i] <= 1e9
-1e9 <= target <= 1e9
只会存在一个有效答案

题解

算法: 哈希

假设选出的两个数为 $i, j$，最直观的想法是先枚举其中第二个数 $j=0,1,\cdots,n-1$，然后再枚举第一个数 $i=0,1,\cdots,j-1$，判断 $A[i] + A[j]$ 是否等于 $t$。这样的话时间复杂度为 $O(N^{2})$。

同样还是先枚举第二个数 $j=0,1,\cdots,n-1$，第一个数肯定来自 $0,1,\cdots,j-1$ 这些数的集合，如果我们将选择第一个数的过程抽象地理解为在集合中查找，那么我们的思路就可以不局限于枚举，自然可以想是不是可以通过数据结构来维护集合的动态变化以及查找操作。

对于集合的动态维护及其查找，如果有维护集合元素的大小顺序的需求，一般考虑平衡树；如果维护大小顺序的需求，一般考虑哈希表。本题没有对大小顺序的需求，只是查找特定值在集合中是否存在，哈希表是最合适的。

由于我们再返回答案的时候需要元素对应的下标，所以这里的哈希表用的是哈希映射，元素作为键，下标为映射到的值。另一方面，由于保证只有一个有效答案，所以没有重复元素的问题。

代码 (C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        int n = nums.size();
        vector<int> result = {-1, -1};
        unordered_map<int, int> mapping;
        for(int j = 0; j < n; ++j)
        {
            if(mapping.count(target - nums[j]) > 0)
            {
                result[0] = mapping[target - nums[j]];
                result[1] = j;
                break;
            }
            mapping[nums[j]] = j;
        }
        return result;
    }
};

代码 (Python)

1
2
3
4
5
6
7
8
9
10
11

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        n = len(nums)
        mapping = {}
        result = [-1, -1]
        for j in range(n):
            if target - nums[j] in mapping:
                result = [mapping[target - nums[j]], j]
                break
            mapping[nums[j]] = j
        return result