# LeetCode 1. 两数之和

LeetCode 1. Two Sum

给定一个整数数组 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]

提示：

• $2$ <= nums.length <= $10^4$
• $- 10^9$ <= nums[i] <= $10^9$
• $- 10^9$ <= target <= $10^9$
• 只存在一个有效答案

进阶：你可以想出一个时间复杂度小于 $O(n^2)$ 的算法吗？

# 思路

解题思路：遍历数组的下标 i ，判断 target - nums[i] 是否存在，若存在，返回 i 以及 数组中值为 target - nums[i] 的元素的下标

本题不仅要判读数值是否存在，还要记录其下标，因此采用哈希 map ，其中，元素值 作为 key ，元素在数组中的索引下标作为 value

# Method: 哈希 map

由于并不需要 key 有序，可以选择 unordered_map

std::unoredered_map

解题步骤：

1. 定义 unodered_map 容器，命名为 map

2. 遍历数组下标 i

   • 查找 target - nums[i] 是否存在于 map 当中
   • 若存在，返回下标 i 以及 与键值 target - nums[i] 对应的 value
   • 否则，将 nums[i] 以及 i 作为键值对添加到 map

代码实现：

vector<int> twoSum(vector<int>& nums, int target) {

    unordered_map<int, int> map;

    for (int i = 0; i < nums.size(); i++) {

        auto temp = map.find(target - nums[i]); //find 返回的是迭代器类型

        if (temp != map.end())                  // 找到 target - nums [i]

            return {temp->second, i};           // 返回 i 以及 temp 的第二个值

                                                //temp->first 是 key ，temp->second 是 value

        map.insert(pair<int, int>(nums[i], i)); // 将 nums [i], i 作为键值对插入到 map

    }

    return {};

}

unordered_map 的成员函数 find 的返回值是 iterator 类型，解引用后的第一个成员为 key ，第二个成员为 value ，详见 std::unordered_map::find

# LeetCode 128. 最长连续序列

128. Longest Consecutive Sequence

给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。

请你设计并实现时间复杂度为 $O(n)$ 的算法解决此问题。

示例 1：

输入：nums = [100,4,200,1,3,2]
输出：4
解释：The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.

示例 2：

输入：nums = [0,3,7,2,5,8,4,6,0,1]
输出：9

提示：

• $0 \le$ nums.length $\le 10^5$
• $-10^9 \le$ nums[i] $\le 10^9$

# Method: 哈希表

算法思路：

定义一个哈希表（记作 hash ，即 unordered_map<int> hash ），将数组中的数字作为哈希表的键，将数字所在的连续序列的最大长度作为对应的哈希表值

遍历数组（记当前遍历到的数字为 num）：

• 若数字 num 已在哈希表中，跳过

• 若数字 num 不在哈希表中：

  • 找出左侧相邻数 num - 1 所在的连续序列的最大长度，记作 left ，即 left = hash [num - 1]

  • 找出右侧相邻数 num + 1 所在的连续序列的最大长度，记作 right ，即 right = hash [num + 1]

  • 将 num 左右两侧的连续序列以及 num 进行拼接，计算新的连续序列的长度：len = left + right + 1

  • 更新当前数字 num 对应的哈希表值，即 hash [num] = len

  • 更新连续序列两个端点对应的哈希表值，即，hash [num - left] = len ，hash [num + right] = len

  • 更新整个数组中的最长连续序列的长度，即 ans = max (ans, len)

上述算法中，拼接 num 及其左右两侧连续序列时，我们没有更新连续序列中每个数字对应的哈希表值，而只是更新两个端点对应的哈希表值。这是因为：区间 (num - left, num + right) 内数字对应的哈希表值不会被使用，只有 num -left 和 num + right 这两个端点对应的哈希表值可能被使用

• 在之后的遍历中，如果遇到 [num - left, num + right] 区间内的数，会直接跳过，无需考察其左右两侧数字所在连续序列的长度
• 在之后的遍历中，如果遇到 num - left - 1（或 num + right + 1），由于 num - left（或 num + right）对应的连续序列长度已经更新，可以直接将 num - left - 1（或 num + right + 1）与 num - left（或 num + right）对应的连续序列进行拼接，无需担心结果出错

无论 num 左右两侧是否存在相应的连续序列，上述算法都能奏效（哈希表的值全都初始化为 0 ）

• 当 num 左侧或右侧不存在连续序列时，left 或 right 为 0，num - left 或 num + right 就是 num 本身
• 当 num 左右两侧均不存在连续序列时，left 和 right 均为 0，num - left 和 num + right 都是 num 本身

代码实现：

int longestConsecutive(vector<int>& nums) {

    unordered_map<int, int> hash; // 哈希表，存储每个数字对应连续序列的长度

    int left = 0;

    int right = 0;

    int len = 0;

    int ans = 0;

    for (int num : nums) {

        if (hash[num] == 0) {

            left = hash[num - 1];     // 左侧数字对应连续序列的长度

            right = hash[num + 1];    // 右侧数字对应连续序列的长度

            len = left + right + 1;   // 拼接左右连续序列

            hash[num] = len;          // 数字 num 对应连续序列的长度

            hash[num - left] = len;   // 更新左侧数字对应序列的端点的键值

            hash[num + right] = len;  // 更新右侧数字对应序列的端点的键值    

            if (len > ans) ans = len; // 更新最大长度     

        }

    }

    return ans;

}

时间复杂度：$O(n)$，其中 $n$ 是数组的长度

空间复杂度：$O(n)$

参考：jalan

# LeetCode 1296. 划分数组为连续数字的集合

1296. 划分数组为连续数字的集合

给你一个整数数组 nums 和一个正整数 k ，请你判断是否可以把这个数组划分成一些由 k 个连续数字组成的集合

如果可以，请返回 true ；否则，返回 false

示例 1：

输入：nums = [1,2,3,3,4,4,5,6], k = 4
输出：true
解释：数组可以分成 [1,2,3,4] 和 [3,4,5,6]

示例 2：

输入：nums = [3,2,1,2,3,4,3,4,5,9,10,11], k = 3
输出：true
解释：数组可以分成 [1,2,3] , [2,3,4] , [3,4,5] 和 [9,10,11]

示例 3：

输入：nums = [3,3,2,2,1,1], k = 3
输出：true

示例 4：

输入：nums = [1,2,3,4], k = 3
输出：false
解释：数组不能分成几个大小为 3 的子数组。

提示：

• $1 \le$ k $\le$ nums.length $\le 10^5$
• $1 \le$ nums[i] $\le 10^9$

# Method: 排序 + 哈希

# 算法思路

题目要求将数组划分成若干个集合，其中，每个集合包含 k 个连续数字

可以从尚未分组的元素中找出值最小的元素，将其作为集合的第一个元素（记作 x ），于是该集合中数字的范围应为 [x, x + k - 1] 。如果某个数字不存在，则无法将数组划分成符合条件的集合，返回 false

将 [x, x + k - 1] 这 k 个元素划分到一个集合之后，继续对数组中剩余的数字进行分组，直到 所有元素均已分组 或者 遇到无法分组的情况

# 代码实现

bool isPossibleDivide(vector<int>& nums, int k) {

    if (nums.size() % k) return false;          // 数组长度无法被 k 整除，返回 false

    sort(nums.begin(), nums.end());             // 将数组按从小到大排序

    unordered_map<int, int> hashmap;

    for (auto num : nums) ++hashmap[num];       // 统计每个数字的出现次数

    for (int i = 0; i < nums.size() / k; ++i) { // 一共有 nums.size () /k 个集合

        int first = 0;                          // 集合中第一个元素的下标

        while (first < nums.size() && hashmap[nums[first]] == 0) { // 寻找未被使用的、值最小的元素

            ++first;

        }

        --hashmap[nums[first]];                 // 将 nums [first] 添加到集合（可用次数减 1 ）

        for (int j = 1; j < k; ++j) {           // 寻找剩余的 k - 1 个元素

            if (hashmap[nums[first] + j] == 0)  // 不存在 nums [first] + j 这个数，数字不连续，返回 false

                return false;

            else                                // 存在 nums [first] + j 这个数，将其可用次数减 1

                --hashmap[nums[first] + j];

        }

    }

    return true;

}

# 复杂度分析

时间复杂度：$O(n \log{n})$，其中，$n$ 为数组的长度

空间复杂度：$O(n)$，考虑哈希表所需空间

# 参考资料

参考：力扣官方题解

# LeetCode 15. 三数之和

LeetCode 15. Three Sum

给你一个整数数组 nums ，判断是否存在三元组 [nums[i] , nums[j] , nums[k]] 满足 i != j 、 i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。

注意：答案中不可以包含重复的三元组。

示例 1：

输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
解释：
    nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
    nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
    nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
    不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
    注意，输出的顺序和三元组的顺序并不重要。

示例 2：

输入：nums = []
输出：[]
解释：唯一可能的三元组和不为 0 。

示例 3：

输入：nums = [0]
输出：[]
解释：唯一可能的三元组和为 0 。

提示：

• $0 \le$ nums.length $\le 3000$
• $- 10^5 \le$ nums[i] $\le 10^5$

# 思路

暴力法查找的时间复杂度为 $O(n^3)$ ，考虑用低复杂度算法

注意：题目要求 “ i != j , i != k , j != k ” 并且 “任意两个三元组不能相同” ，故而需要在查找时进行剪枝以避免重复，或是查找结束后剔除重复三元组

本题的难点也在于如何去除重复解

首先，可以对数组进行排序（最终只需要输出元素值即可，无需输出元素索引，故而可以打乱原数组顺序），将重复的元素值集中，便于去重

于是，有以下两种方法可以用于查找：

1. 哈希法：采用两层 for 循环分别遍历 i 和 j （按照从左往右的顺序），并采用哈希法检查 [i, j] 区间范围内是否有元素能与 nums[i] ， nums[j] 组成三元组

2. 双指针法：采用一个 for 循环遍历 i ，并采用双指针法在 [i + 1, nums.size() - 1] 区间内查找所有能与 nums[i] 组成三元组的元素 nums[left] 和 nums[right] ，其中，指针 left 从 i + 1 位置开始向右遍历，指针 right 从 nums.size() - 1 位置开始向左遍历

两种方法都能实现 $O(n^2)$ 的时间复杂度，但哈希法不便进行去重操作，因此，建议使用排序与双指针法解题

# Method: 排序 + 双指针

解题步骤：

1. 对数组进行排序（从小到大排序）

2. 遍历数组下标 i

   • 若 nums[i] > 0 ，则 i 右侧不存在能与 nums[i] 组成三元组的元素，直接返回结果

   • 若 i > 0 && nums[i] == nums[i - 1] ，当前 i 能找到的三元组与 i - 1 时找到的完全相同，为避免产生重复解，跳过当前 i

   • 定义指针 left 指向 i + 1 位置，指针 right 指向 nums.size() - 1 位置，当 left < right 时，执行循环：

     • 计算 sum = nums[i] + nums[left] + nums[right]
     • 若 sum > 0 ，则 nums[right] 偏大，将 right 左移
     • 若 sum < 0 ，则 nums[left] 偏小，将 left 右移
     • 若 sum == 0 ，记录结果，并将 left 右移、将 right 左移，以跳过重复的 nums[left] 和 nums[right]

注意：同一个 i 可以与不同的元素组成多个不同的三元组，因此，在找到一对可行的 nums[left] 和 nums[right] 后仍需继续查找，直到 left < right 不满足

代码实现：

vector<vector<int>> threeSum(vector<int>& nums) {

    sort(nums.begin(), nums.end()); // 排序

    vector<vector<int>> res;        // 存储结果

    for (int i = 0; i < nums.size(); i++) {

        if (nums[i] > 0) break;

        if (i > 0 && nums[i] == nums[i - 1]) continue;

        int left = i + 1, right = nums.size() - 1;

        int sum = 0;

        while (left < right) {

            sum = nums[i] + nums[left] + nums[right];

            if (sum > 0) right--;

            if (sum < 0) left++;

            if (sum == 0) {

                res.push_back(vector<int>{nums[i], nums[left], nums[right]});

                // 将 left 右移（注意，++left 至少执行一次）

                while (left < right && nums[left] == nums[++left]);

                // 将 right 左移（注意，--right 至少执行一次）

                while (left < right && nums[right] == nums[--right]);

            }

        }

    }

    return res;

}

需要注意的第一个地方：

if (i > 0 && nums[i] == nums[i - 1]) continue;

这里不能改成 if (nums[i] == nums[i + 1]) continue; ，否则，以数组 nums = [-1, 0, 1, 2, -1, -4] 为例（排序后， nums = [-4, -1, -1, 0, 1, 2] ），查找时将会遗漏 [-1, -1, 2] 这一个三元组。因为当 i = 1 时 nums[1] == nums[2] 条件成立，因此不会进行双指针查找；而当 i = 2 时，只会查找 i 右侧的元素，故而遗失了对 [-1, -1, x] 这几种情况的查找， x 为第二个 -1 右侧的任意值

<!-- 上述的 Method 1 也是类似道理 -->

需要注意的第二个地方：

if (sum == 0) {
    res.push_back(vector<int>{nums[i], nums[left], nums[right]});
    while (left < right && nums[left] == nums[++left]);
    while (left < right && nums[right] == nums[--right]);
}

这里的 ++left 和 --right 都至少执行一次：执行一次是因为找到了一个三元组，需要同时移动双指针，以进行下一次的查找；执行多次则是为了跳过重复的 nums[left] 和 nums[right]

并且，注意这里的 nums[left] == nums[++left] 语句，将当前 left 对应元素值与 left 右移之后对应元素值进行比较，不能将其改成 nums[++left] == nums[left] ，也不能改成 nums[left] == nums[left++] 。语句 nums[right] == nums[--right] 同理

特别地，第二个地方可以改写成

if (sum == 0) {
    res.push_back(vector<int>{nums[i], nums[left], nums[right]});
    // 先将 left 移到最靠右的一个 nums[left]
    while (left < right && nums[left] == nums[left + 1]) left++;
    // 先将 right 移到最靠左的一个 nums[right]
    while (left < right && nums[right] == nums[right - 1]) right--;
    // 再分别移动一次 left 和 right ，以进行下一次查找
    left++;
    right--;
}

另外，当 sum > 0 时，可对 nums[right] 进行去重，以跳过重复的 nums[right] ，即，将 if (sum > 0) right--; 改写为

if (sum > 0)
    while (left < right && nums[right] == nums[--right]);

或者改写为

if (sum > 0) {
    right--;
    while (left < right && nums[right] == nums[right + 1]) right--;
}

类似地，当 sum < 0 时，也可对 nums[left] 进行去重，以跳过重复的 nums[left]

时间复杂度：$O(n^2)$

• 遍历 i ：$O(n)$
• 双指针查找：$O(n)$

空间复杂度：$O(\log{n})$

• 不考虑存储结果的数组
• 仅考虑排序所需栈空间

参考：

• 代码随想录：三数之和
• Krahets：三数之和（排序 + 双指针，易懂图解）

# LeetCode 18. 四数之和

LeetCode 18. Four Sum

给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] （若两个四元组元素一一对应，则认为两个四元组重复）：

• 0 <= a, b, c, d < n
• a 、 b 、 c 和 d 互不相同
• nums[a] + nums[b] + nums[c] + nums[d] == target

你可以按 任意顺序 返回答案 。

示例 1：

输入：nums = [1,0,-1,0,-2,2], target = 0
输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]

示例 2：

输入：nums = [2,2,2,2,2], target = 8
输出：[[2,2,2,2]]

提示：

• $1 \le$ nums.length $\le 200$
• $- 10^9 \le$ nums[i] $\le 10^9$
• $- 10^9 \le$ target $\le 10^9$

# 思路

需注意区分本题与 LeetCode 454. 四数相加 II

本题的解题方法与 LeetCode 15. 三数之和 基本一致，这里采用 排序 + 双指针 解法

# Method: 排序 + 双指针

解题思路：

1. 对数组 nums 排序

2. 采用两个 for 循环分别遍历 i 和 j ，其中， i 从 0 开始遍历， j 从 i + 1 开始遍历（注意，要分别对 nums[i] 和 nums[j] 进行去重）

3. 采用双指针法在 [j + 1, nums.size() - 1] 区间内查找所有能与 nums[i] , nums[j] 组成四元组的元素 nums[left] 和 nums[right] ，其中，指针 left 从 j + 1 位置开始向右遍历，指针 right 从 nums.size() - 1 位置开始向左遍历

具体步骤可参考 LeetCode 15. 三数之和

代码实现：

vector<vector<int>> fourSum(vector<int>& nums, int target) {

    sort(nums.begin(), nums.end());

    vector<vector<int>> res;

    for (int i = 0; i < nums.size(); i++) {

        if (i > 0 && nums[i] == nums[i - 1]) continue; // 对 nums [i] 去重

        for (int j = i + 1; j < nums.size(); j++) {

            if (j > i + 1 && nums[j] == nums[j - 1]) continue; // 对 nums [j] 去重

            int left = j + 1, right = nums.size() - 1;

            int temp = nums[i] + nums[j]; // 直接计算 nums [i] + nums [j] + nums [left] + nums [right] 会溢出

            while (left < right) {

                if (nums[left] + nums[right] < target - temp) left++;

                else if (nums[left] + nums[right] > target - temp) right--;

                else {

                    res.push_back({nums[i], nums[j], nums[left], nums[right]});

                    while (left < right && nums[left] == nums[++left]); // 对 nums [left] 去重

                    while (left < right && nums[right] == nums[--right]); // 对 nums [right] 去重

                }

            }

        }

    }

    return res;

}

其中，需要注意 nums[i] + nums[j] + nums[left] + nums[right] 会溢出，因此，不能直接将 nums[i] + nums[j] + nums[left] + nums[right] 与 target 比较，可比较 nums[left] + nums[right] 与 target - nums[i] - nums[j]

另外，当 temp2 < target - temp1 时，可跳过重复的 nums[left] ，当 temp2 > target - temp1 时，可跳过重复的 nums[right] ，即，将第 12 至 13 行代码改写为：

if (temp2 < target - temp1)
    while (left < right && nums[left] == nums[++left]);
else if (temp2 > target - temp1)
    while (left < right && nums[right] == nums[--right]);

具体可见 LeetCode 15. 三数之和

时间复杂度：$O(n^3)$

• 遍历 i 和 j ：$O(n^2)$
• 双指针查找：$O(n)$

空间复杂度：$O(\log{n})$ ，这里不考虑存储结果的数组，仅考虑排序所需栈空间

参考：代码随想录：四数之和

# LeetCode 202. 快乐数

LeetCode 202. Happy Number

编写一个算法来判断一个数 n 是不是快乐数。

快乐数 定义为：

• 对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。
• 然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。
• 如果这个过程 结果为 1，那么这个数就是快乐数。

如果 n 是 快乐数 就返回 true ；不是，则返回 false 。

示例 1：

输入：n = 19
输出：true
解释：
    1 + 81 = 82
    64 + 4 = 68
    36 + 64 = 100
    1 + 0 + 0 = 1

示例 2：

输入：n = 2
输出：false

提示：

• $1 \le$ n $\le 2^{31} - 1$

# 思路

注意到题目说明：

• 若各位平方和最终等于 1 ，则 n 为快乐数
• 若各位平方和的值循环出现，则 n 不是快乐数

因此，本题的解题关键在于，在求和过程中，判断数字是否重复出现

• 若重复出现，则该数字必定不是快乐数
• 若求和结果为 1，则该数字是快乐数

# Method 1: 哈希 set

std::unordered_set

考虑用哈希表 unordered_set 记录求和过程中出现的数字，并判断其是否重复出现

另，需注意 n 的各位数字平方和的计算

• 计算个位数字的平方
• 取个位以外的部分
• 重复以上两步

代码实现：

int getSum(int n) { // 计算 n 中各位的平方和

    int sum = 0;

    while (n) {

        sum += (n % 10) * (n % 10); // 取 n 的个位数，求其平方，再累加到 sum 上

        n /= 10;                    // 取个位数以外的部分

    }

    return sum;

}

bool isHappy(int n) {

    unordered_set<int> record;

    while (1) {

        int sum = getSum(n);

        if (sum == 1)

            return 1;

        if (record.find(sum) != record.end()) //sum 重复出现

            return 0;

        else

            record.insert(sum);               //sum 第一次出现

        n = sum;                              // 更新当前计算数字

    }

}

代码随想录：快乐数

时间复杂度：$O(\log{n})$

• 查找给定数字的下一个值的时间复杂度为 $O(\log{n})$ ，因为数字的位数由 $O(\log_{10}{n}) = O(\log{n})$ 确定
• 总体的时间复杂度还需考虑循环过程中的数字个数，这里简单起见仅考虑计算下一个值的时间复杂度

空间复杂度：$O(\log{n})$

# Method 2: 快慢指针

可以采用类似于 LeetCode 142. 环形链表 II 的方法，定义快慢指针，判断是否存在环

• 若存在环，则快慢指针一定会在环内相遇，即，数 n 不是快乐数
• 否则，快指针会比慢指针先到达数字 1 ，即，数 n 是快乐数

力扣官方题解：快乐数

# LeetCode 242. 有效的字母异位词

LeetCode 242. Valid Anagram

给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。

注意：若 s 和 t 中每个字符出现的次数都相同，则称 s 和 t 互为字母异位词。

示例 1：

输入：s = "anagram", t = "nagaram"
输出：true

示例 2：

输入：s = "rat", t = "car"
输出：false

提示：

• $1 \le$ s.length , t.length $\le 5 \times 10^4$
• s 和 t 仅包含小写字母

进阶：如果输入字符串包含 unicode 字符怎么办？你能否调整你的解法来应对这种情况？

# 思路

字母异位词，等价于，两个字符串中字符出现的种类和次数均相等

利用数组 cnt 来实现一个简单的哈希表，将字符 a 到 z 映射为数组的下标 0 到 25 ，数组的元素值表示相应字符在字符串 s 和 t 里出现的次数的差值

若 cnt 所有元素值均为 0，字符串 s 和 t 是字母异位词

代码实现：

bool isAnagram(string s, string t) {

    vector<int> cnt(26, 0);     // 计算 s 和 t 各个字母出现次数的差值

    for (auto c : s)

        cnt[c - 'a']++;         // 记录字符串 s 中字符出现的次数

    for (auto c : t)

        cnt[c - 'a']--;         // 记录字符串 t 中字符出现次数的相反数

    for (int i = 0; i < 26; i++)

        if (cnt[i] != 0)        //cnt 元素不为 0 ，则字符串 s 和 t 中的字符不同，不是字母异位词

            return 0;

    return 1;                   // 所有字符出现次数相同，是 s 和 t 是字母异位词

}

时间复杂度：$O(n)$

空间复杂度：$O(1)$，常量大小的辅助数组

这一题使用数组来实现哈希法，是因为题目限制了只有 26 个小写字母，哈希值比较集中

# LeetCode 349. 两个数组的交集

LeetCode 349. Intersection of Two Arrays

给定两个数组 nums1 和 nums2 ，返回 它们的交集 。输出结果中的每个元素一定是 唯一 的。我们可以 不考虑输出结果的顺序 。

示例 1：

输入：nums1 = [1,2,2,1], nums2 = [2,2]
输出：[2]

示例 2：

输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出：[9,4]
解释：[4,9] 也是可通过的

提示：

• $1 \le$ nums1.length , nums2.length $\le 1000$
• $0 \le$ nums1[i] , nums2[i] $\le 1000$

# 思路

由于数组 nums1 和 nums2 的元素值可能比较分散，使用数组来实现哈希法会造成空间的浪费，故而可以采用 set

注意到题目要求输出的每个元素必须唯一，且不考虑输出结果的顺序，故而选用 unordered_set

注：相比于数组而言，直接使用 set 不仅占用空间比数组大，而且速度慢。因此，在 数组元素大小有限 且 哈希值比较集中 时，应尽量用 数组 ，而如果哈希值比较少、特别分散、跨度非常大，则考虑用 set

# unordered_set

解题步骤：

1. 定义 unordered_set 容器 record 和 ans ，前者存放第一个数组 nums1 的元素，后者记录两数组的交集

2. 遍历数组 nums2 ：若 nums2 数组的元素 a 能够在 record 中找到（即， record.find(a) != record.end() ），则说明 a 是两数组的公共元素，将其添加到 ans 中

代码实现：

vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {

    unordered_set<int> record(nums1.begin(), nums1.end());  // 将 nums1 拷贝到 unordered_set 容器

    unordered_set<int> ans;             // 存放结果（两数组的交集）

    for (auto a : nums2)

        if (record.find(a) != record.end())   //nums2 的元素 a 在 nums1 中出现过

            ans.insert(a);              // 将 a 添加到结果

    return vector<int>(ans.begin(), ans.end());   // 返回（先拷贝到 vector ，因为返回值的类型是 vector<int>）

}

# LeetCode 383. 赎金信

LeetCode 383. Ransom Note

给你两个字符串： ransomNote 和 magazine ，判断 ransomNote 能不能由 magazine 里面的字符构成。

如果可以，返回 true ；否则返回 false 。

magazine 中的每个字符只能在 ransomNote 中使用一次。

示例 1：

输入：ransomNote = "a", magazine = "b"
输出：false

示例 2：

输入：ransomNote = "aa", magazine = "ab"
输出：false

示例 3：

输入：ransomNote = "aa", magazine = "aab"
输出：true

提示：

• $1 \le$ ransomNote.length , magazine.length $\le 10^5$
• ransomNote 和 magazine 由小写英文字母组成

# Method: 哈希

由于字符串中只有小写字母，可以考虑用 数组 实现哈希法

解题步骤如下：

1. 定义数组 count ，数组元素的下标表示字符相当于 a 的距离，元素值表示字符在字符串 magazine 中出现的次数

2. 依据数组 count 判断 ransomNote 的每个字符是否都在字符串 magazine 内

   • 由于 magazine 中每个字符只能在 ransomNote 中用一次，在遍历字符串 ransomNote 中的每个字符时，需要维护字符所对应的 count 元素值，即，“用一次就会少一次”

代码实现：

bool canConstruct(string ransomNote, string magazine) {

    vector<int> count(26, 0); // record the letters and their frequency in string magazine

    for (auto c : magazine)

        count[c - 'a']++;

    for (auto c : ransomNote) {

        if (count[c - 'a'])

            count[c - 'a']--; // since each letter in string magazine can only be used once

        else

            return false;     // c cannot be found in string magazine

    }

    return true;

}

时间复杂度：$O(n)$

空间复杂度：$O(1)$

由于 ransomNote 和 magazine 都由字母组成， key 分布较为集中。与 set 和 map 相比，采用数组更为省时

# LeetCode 438. 找到字符串中所有字母异位词

438. Find All Anagrams in a String

给定两个字符串 s 和 p ，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。

异位词 指由相同字母重排列形成的字符串（包括相同的字符串）。

示例 1：

输入：s = "cbaebabacd", p = "abc"
输出：[0,6]
解释：
    起始索引等于 0 的子串是 "cba", 它是 "abc" 的异位词。
    起始索引等于 6 的子串是 "bac", 它是 "abc" 的异位词。

示例 2：

输入：s = "abab", p = "ab"
输出：[0,1,2]
解释：
    起始索引等于 0 的子串是 "ab", 它是 "ab" 的异位词。
    起始索引等于 1 的子串是 "ba", 它是 "ab" 的异位词。
    起始索引等于 2 的子串是 "ab", 它是 "ab" 的异位词。

提示：

• $1 \le$ s.length , p.length $\le 3 \times 10^4$
• s 和 p 仅包含小写字母

# Method: 滑动窗口法

算法思路：

可以在字符串 s 中构造一个与字符串 p 长度相同的滑动窗口，并在滑动窗口过程中维护每种字母的数量。当每种字母在窗口中的数量等于其在字符串 p 中的数量时，窗口即为字符串 p 的异位词

特别地，可做以下考虑：

• 用哈希表来统计滑动窗口与字符串 p 中每种字母的数量差。当某个字母对应的数量差为 0 时，字母在窗口中的数量等于其在字符串 p 中的数量

• 用变量 valid 来记录数量差为 0 的字母的种类数。当 valid 等于哈希表的长度时，窗口就是字符串 p 的字母异位词

代码实现：

vector<int> findAnagrams(string s, string p) {

    vector<int> ans; // 结果数组

    int sLen = s.size();

    int pLen = p.size();

    if (sLen < pLen) return ans;

    unordered_map<char, int> record;

    for (auto c : p)

        ++record[c]; //record [c] 表示需添加到窗口内的字符 c 的数量

    int left = 0;    // 滑动窗口的左边界

    int right = 0;   // 滑动窗口的右边界

    int valid = 0;   // 窗口内已满足数量要求的字符种类数

    while (right < sLen) {

        char c = s[right];

        // 更新窗口的相关数据

        if (record.count(c)) {            // 仅当 p 字符串包含的字符 c 时更新 record 和 valid

            --record[c];                  //c 添加到窗口内，所需字符 c 的数量应减 1

            if (record[c] == 0)           // 字符 c 的数量满足要求，有效字符数加 1

                ++valid;

        }

        // 判断是否需要收缩窗口

        while (right - left + 1 > pLen) { // 窗口长度大于 pLen ，应收缩窗口

            char d = s[left];

            // 更新窗口的相关数据

            if (record.count(d)) {        // 仅当 p 字符串包含的字符 d 时更新 record 和 valid

                if (record[d] == 0)       // 目前字符 d 满足数量要求，但其将被移出，故有效字符数减 1

                    --valid;

                ++record[d];              //d 从窗口内移出，所需字符 d 的数量应加 1

            }

            ++left;                       // 窗口的左边界向右移动

        }

        // 窗口符合条件时，将起始索引加入目标数组

        if (right - left + 1 == pLen) {   // 窗口长度等于字符串 p 长度

            if (valid == record.size())   // 所有字符均满足数量要求，将索引添加到目标数组

                ans.push_back(left);

        }

        ++right;                          // 窗口的右边界向右移动

    }

    return ans;

}

时间复杂度：$O(n + m)$，其中，$n$ 为字符串 s 的长度，$m$ 为字符串 p 的长度

空间复杂度：$O(\vert \Sigma \vert)$，其中，$\vert \Sigma \vert$ 为字符串 p 中的字符种类数

参考：

• labuladong
• leetcode-solution

# LeetCode 454. 四数相加 II

LeetCode 454. 4Sum II

给你四个整数数组 nums1 、 nums2 、 nums3 和 nums4 ，数组长度都是 n ，请你计算有多少个元组 (i, j, k, l) 能满足：

• 0 <= i, j, k, l < n

• nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0

示例 1：

输入：nums1 = [1,2], nums2 = [-2,-1], nums3 = [-1,2], nums4 = [0,2]
输出：2
解释：两个元组如下：
    1. (0, 0, 0, 1) -> nums1[0] + nums2[0] + nums3[0] + nums4[1] = 1 + (-2) + (-1) + 2 = 0
    2. (1, 1, 0, 0) -> nums1[1] + nums2[1] + nums3[0] + nums4[0] = 2 + (-1) + (-1) + 0 = 0

示例 2：

输入：nums1 = [0], nums2 = [0], nums3 = [0], nums4 = [0]
输出：1

提示：

• n == nums1.length
• n == nums2.length
• n == nums3.length
• n == nums4.length
• $1 \le$ n $\le 200$
• $- 2^{28} \le$ nums1[i] , nums2[i] , nums3[i] , nums4[i] $\le 2^{28}$

# 思路

统计 nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0 成立的 (i, j, k, l) 的个数，不用考虑是否有重复的元素值相加

可以采用 unordered_map 容器记录 任意 nums1[i] 与 nums2[j] 相加的和，将其作为 key ，同时记录 该 key 值出现的次数，将其作为对应的 value

然后遍历 nums3[k] 和 nums4[l] ，看 unordered_map 容器中是否能找到值为 0 - num3[k] - num4[l] 的 key ，将找到的所有 key 对应的 value 进行求和，即为所求

# 哈希 map

解题步骤：

1. 定义一个 unordered_map 容器，命名为 map
2. 遍历数组 nums1 的元素 a 和 数组 nums2 的元素 b ，将 a + b 作为哈希 map 的 key ，将值 a + b 出现的次数作为对应的 value
3. 定义变量 count ，用来记录答案
4. 遍历数组 nums3 元素 c 和数组 nums4 元素 d ，如果在哈希 map 中找到 0 - (c + d) ，把对应的 value 累加到 count

代码实现：

int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {

    // 统计 nums1 和 nums2 数组中任意两元素之和

    unordered_map<int, int> map;

    for (auto a : nums1)

        for (auto b : nums2)

            map[a + b]++;

    // 统计 a + b + c + d = 0 的次数

    int count = 0;

    for (auto c : nums3)

        for (auto d : nums4)

            if (map.find(0 - c - d) != map.end())

                count += map[0 - c - d];

    return count;

}

时间复杂度：$O(n^2)$

• 两个 for 循环，时间复杂度为 $O(n^2)$
• 每次哈希查找的时间复杂度为 $O(1)$

空间复杂度：$O(n^2)$，哈希 map 所需要的空间

参考：代码随想录：四数相加 II

# LeetCode 49. 字母异位词分组

49. Group Anagrams

给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。

字母异位词 是由重新排列源单词的字母得到的一个新单词，所有源单词中的字母通常恰好只用一次。

示例 1：

输入：strs = ["eat","tea","tan","ate","nat","bat"]
输出：[["bat"],["nat","tan"],["ate","eat","tea"]]

示例 2：

输入：strs = [""]
输出：[[""]]

示例 3：

输入：strs = ["a"]
输出：[["a"]]

提示：

• $1 \le$ strs.length $\le 10^4$
• $0 \le$ strs[i].length $\le 100$
• strs[i] 仅包含小写字母

# Method 1: 排序 + 哈希

算法思路：

两个字符串互为字母异位词，当且仅当它们包含的字母相同，因此，对两个字母异位词分别进行排序，所得的字符串一定相同

可以将排序之后的字符串作为哈希表的键，哈希表的值存放每一组字母异位词

代码实现：

vector<vector<string>> groupAnagrams(vector<string>& strs) {

    unordered_map<string, vector<string>> hash;

    for (auto &s : strs) {

        string key = s;

        sort(key.begin(), key.end());

        hash[key].push_back(s);

    }

    vector<vector<string>> ans;

    for (auto it = hash.begin(); it != hash.end(); it++) {

        ans.push_back(it->second);

    }

    return ans;

}

时间复杂度：$O(n k \log{k})$，其中，$n$ 是 strs 的长度，$k$ 是 strs 中字符串的最大长度

• 遍历 strs 的时间复杂度为 $O(n)$
• 对 strs 中的每个字符串进行排序，时间复杂度为 $O(k \log{k})$
• 哈希查找的时间复杂度为 $O(1)$

空间复杂度：$O(n k)$，需要用哈希表存储所有字母异位词

# Method 2: 计数 + 哈希

算法思路：

两个字母异位词中的每一种字母的出现次数一定相同

可以使用字符串表示字母的出现次数，将其作为哈希表的键

参考：leetcode-solution

# LeetCode 554. 砖墙

你的面前有一堵矩形的、由 n 行砖块组成的砖墙。这些砖块高度相同（也就是一个单位高）但是宽度不同。每一行砖块的宽度之和相等。

你现在要画一条 自顶向下 的、穿过 最少 砖块的垂线。如果你画的线只是从砖块的边缘经过，就不算穿过这块砖。你不能沿着墙的两个垂直边缘之一画线，这样显然是没有穿过一块砖的 。

给你一个二维数组 wall ，该数组包含这堵墙的相关信息。其中， wall[i] 是一个代表从左至右每块砖的宽度的数组。你需要找出怎样画才能使这条线 穿过的砖块数量最少 ，并且返回 穿过的砖块数量 。

示例 1：

输入：wall = [[1,2,2,1],[3,1,2],[1,3,2],[2,4],[3,1,2],[1,3,1,1]]
输出：2

示例 2：

输入：wall = [[1],[1],[1]]
输出：3

提示：

• n == wall.length
• $1 \le$ n $\le 10^4$
• $1 \le$ wall[i].length $\le 10^4$
• $1 \le$ sum(wall[i].length) $\le 2 \times 10^4$
• 对于每一行 i ， sum(wall[i]) 是相同的
• $1 \le$ wall[i][j] $\le 2^{31} - 1$

# Method: 哈希

# 算法思路

穿过最少的砖块 等价于 穿过最多的间隙

可以使用哈希表记录每个间隙的出现次数（以间隙索引位置为 key ，以间隙出现次数为 value），然后从所有行中找出间隙最大出现次数，利用 行数 减去 间隙出现最大次数 即为 穿过砖块最小数

其中，每一行中的间隙的索引 需要按 前缀和 方法求得，例如，第一行的第一个间隙的索引为 wall[0][0] ，第二个间隙的索引为 wall[0][0] + wall[0][1] ，第 i 个间隙的索引为 wall[0][0] + ... + wall[0][i]

注意：不能沿着砖墙两侧的最边缘画线，因此不需要统计砖墙两侧的间隙

如下图所示，间隙 4 在所有行中出现次数最多，出现次数为 4 次，而总行数为 6 ，因此穿过砖块数为 2

# 代码实现

int leastBricks(vector<vector<int>>& wall) {

    unordered_map<int, int> hash;

    for (int i = 0; i < wall.size(); ++i) {

        int sum = 0;

        for (int j = 0; j < wall[i].size() - 1; ++j) { // 不能沿着最边缘画线

            sum += wall[i][j];                         // 间隙的索引

            ++hash[sum];

        }

    }

    int maxCnt = 0;

    for (auto it : hash) {

        maxCnt = max(maxCnt, it.second);

    }

    return wall.size() - maxCnt;

}

# 复杂度分析

时间复杂度：$O(n)$，其中 $n$ 为砖块总个数

空间复杂度：$O(n)$

# 参考资料

• 宫水三叶：使用哈希表求解
• 力扣官方题解