本文主要涉及数组、哈希表、排序、二分查找、双指针等内容

存在重复元素
二分查找
有序数组的平方
移除元素
长度最小的子数组

剑指 Offer 03. 数组中重复的数字

下一个排列
多数元素
除自身以外数组的乘积
搜索二维矩阵 II
寻找重复数
找到所有数组中消失的数字
和为 K 的子数组
最短无序连续子数组

# LeetCode 217. 存在重复元素

LeetCode 217. Contains Duplicate

给你一个整数数组 nums 。如果任一值在数组中出现 至少两次 ，返回 true ；如果数组中每个元素互不相同，返回 false 。

示例 1：

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

示例 2：

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

示例 3：

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

提示：

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

# Method 1: 排序

若采取两个循环嵌套进行暴力查找，时间复杂度为 $O(N^2)$ ，将超出时间限制

可以先对数组 nums 进行排序，检查相邻两元素是否相等

bool containsDuplicate(vector<int>& nums) {
    sort(nums.begin(), nums.end());
    int n = nums.size();
    for (int i = 0; i < n - 1; i++) {
        if (nums[i] == nums[i + 1]) return true;
    }
    return false;
}

时间复杂度： $O(N \log N)$ ，其中 $N$ 为数组长度。因为需要对数组排序

空间复杂度： $O(\log N)$ ，其中 $N$ 为数组长度。注意我们在这里应当考虑递归调用栈的深度

# Method 2: 哈希表 set

可以尝试将数组中每个元素都插入到哈希表 unordered_set 中：如果插入一个元素时发现该元素已经存在于哈希表中，则说明存在重复的元素

bool containsDuplicate(vector<int>& nums) {
    unordered_set<int> set;
    for (auto c : set) { // c 是 int 型
        if (set.find(c) != set.end()) return true;  // 找到 c 的位置不在尾后，即，哈希表中存在元素 c
        set.insert(c);   // 将 c 插入到哈希表中
    }
    return false;

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

空间复杂度： $O(N)$ ，其中 $N$ 为数组的长度

# Method 3: 哈希表 map

也可以直接用 unordered_map 容器统计每一个元素出现的次数，然后遍历整个 unordered_map 容器查看是否有元素出现的次数大于等于 2

bool containsDuplicate(vector<int>& nums) {
    unordered_map<int,int> map;
    for(int num : nums) {
        map[num]++;
        if(map[num] >= 2) return true;
    }
    return false;
}

# LeetCode 704. 二分查找

LeetCode 704. Binary Search

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数，在 $O(\log n)$ 时间复杂度下搜索 nums 中的 target ，如果目标值存在返回下标，否则返回 -1 。

示例 1：

输入：nums = [-1,0,3,5,9,12], target = 9
输出：4
解释：9 exists in nums and its index is 4

示例 2：

输入：nums = [-1,0,3,5,9,12], target = 2
输出：-1
解释：2 does not exist in nums so return -1

提示：

$1 \le$ nums.length $\le 10^4$
$- 10^4$ < nums[i] , target < $10^4$
nums 中的所有元素不重复
nums 升序排列

# 思路

有序数组，且数组中无重复元素，考虑用二分法

然而，二分查找涉及的很多的 边界条件 ，例如，是 while(left < right) 还是 while(left <= right) 呢，是 right = middle 还是 right = middle - 1 呢？

在二分查找的过程中，要保持不变量，就是在 while 寻找中每一次边界的处理都要坚持根据 区间的定义 来操作，这就是 循环不变量 规则

写二分法，区间的定义一般为两种，左闭右闭，即 [left, right] ，或者 左闭右开，即 [left, right)

# Method 1

定义 target 是在一个在 左闭右闭 的区间里，也就是 [left, right] ，所以有：

right 初值赋为 nums.size() - 1 ，因为 target 定义在 [left, right] 区间内
while (left <= right) 循环控制条件使用 <= ：因为 left == right 是依然可行的
if (nums[middle] > target) 的执行语句中， right 要赋值为 middle - 1 ：因为当前这个 nums[middle] 一定不是 target ，可以更新区间右端点为 nums[middle]

代码实现：

int search(vector<int>& nums, int target) {
    int left = 0;
    int right = nums.size() - 1; // 定义target在左闭右闭的区间里，[left, right]
    while (left <= right) {      // 当left==right，区间[left, right]依然有效，所以用 <=
        int middle = left + ((right - left) / 2);// 防止溢出 等同于(left + right)/2
        if (nums[middle] > target)
            right = middle - 1;  // target 在左区间，所以[left, middle - 1]
        else if (nums[middle] < target)
            left = middle + 1;   // target 在右区间，所以[middle + 1, right]
        else                     // nums[middle] == target
            return middle;       // 数组中找到目标值，直接返回下标
    }
    // 未找到目标值
    return -1;
}

# Method 2

如果定义 target 在一个在 左闭右开 的区间里，也就是 [left, right) ：

right 初值赋为 nums.size() ，因为 target 定义在 [left, right) 区间内
while (left < right) 循环控制条件使用 < ：因为 left == right 在区间 [left, right) 是不可行的
if (nums[middle] > target) 的执行语句中， right 更新为 middle ：因为搜索区间是左闭右开区间，而当前的 nums[middle] 不等于 target ，所以 right 更新为 middle 时，下一个搜索区间就不会再去比较 nums[middle] （注意，这里不能将 right 更新为 middle - 1 ：若 right 赋值为 middle - 1 ，则排除了 middle - 1 的可能性）

int search(vector<int>& nums, int target) {
    int left = 0;
    int right = nums.size();    // 定义target在左闭右开的区间里，即：[left, right)
    while (left < right) {      // 因为left == right在区间[left, right)是不可行的，所以使用 <
        int middle = left + ((right - left) >> 1); // 等同于left + ((right - left) / 2)
        if (nums[middle] > target)
            right = middle;     // target 在左区间，在[left, middle)中
        else if (nums[middle] < target)
            left = middle + 1;  // target 在右区间，在[middle + 1, right)中
        else                    // nums[middle] == target
            return middle;      // 数组中找到目标值，直接返回下标
    }
    // 未找到目标值
    return -1;
}

在循环中要坚持根据搜索区间的定义来做边界处理

参考：代码随想录：704. 二分查找

# LeetCode 977. 有序数组的平方

LeetCode 977. Squares of a Sorted Array

给你一个按 非递减顺序 排序的整数数组 nums ，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。

示例 1：

输入：nums = [-4,-1,0,3,10]
输出：[0,1,9,16,100]
解释：平方后，数组变为 [16,1,0,9,100] 。排序后，数组变为 [0,1,9,16,100]

示例 2：

输入：nums = [-7,-3,2,3,11]
输出：[4,9,9,49,121]

提示：

$1 \le$ nums.length $\le 10^4$
$-10^4 \le$ nums[i] $\le 10^4$
nums 已按非递减顺序排序

# Method 1: 双指针

解题思路：

找出非递减数组 nums 中正负整数的分界线 pos ，假定 nums[pos] <= 0 。当我们将数组 nums 中的数平方后，第 0 位到第 pos 位将单调递减，第 pos + 1 位到第 n − 1 位将单调递增
创建 ans 数组，令指针 i 和 j 分别指向 pos 和 pos + 1 ，分以下情况进行操作（类似于归并操作）：
- 如果 i < 0 ，或者， j < nums.size() 且 nums[i] * nums[i] >= nums[j] * nums[j] ，则填充 nums[j] * nums[j] ，并执行 j++
- 否则，填充 nums[i] * nums[i] ，并执行 i--

代码实现：

vector<int> sortedSquares(vector<int>& nums) {
    // 找到最大的负数或者零所在的位置，即，正负数分界线
    int mid = -1;
    for (int i = 0; i < nums.size(); i++) {
        if (nums[i] < 0)
            mid = i;
        else
            break;
    }

    // 将结果填充到 ans 数组中（类似于归并操作）
    vector<int> ans;
    int i = mid, j = mid + 1;
    while (j - i <= nums.size()) {
        // 如果 i 超出边界，或者，j 未超出边界且 nums[i] 的平方大于 nums[j] ，则填充 nums[j] * nums[j]
        if ((i < 0) || (j < nums.size() && nums[i] * nums[i] >= nums[j] * nums[j])) {
            ans.push_back(nums[j] * nums[j]);
            j++;
        }
        // 否则，填充 nums[i] * nums[i]
        else {
            ans.push_back(nums[i] * nums[i]);
            i--;
        }
    }
    return ans;
}

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

空间复杂度： $O(n)$ ，使用了额外的数组

# Method 2: 双指针

使用两个指针分别指向位置 0 和 n − 1 ，每次比较两个指针对应的数，选择较大的并按照逆序放入答案数组，然后移动指针

代码实现：

vector<int> sortedSquares(vector<int>& nums) {
    int n = nums.size();
    vector<int> ans(n, 0);     // 注意这里要初始化
    for (int i = 0, j = n - 1, k = n - 1; i <= j;) {
        if (nums[i] * nums[i] > nums[j] * nums[j]) {
            ans[k] = nums[i] * nums[i];
            i++;
        }
        else {
            ans[k] = nums[j] * nums[j];
            j--;
        }
        k--;
    }
    return ans;
}

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

空间复杂度： $O(n)$ ，使用了额外的数组

另，由于数组按递增顺序排列，可以直接比较 - nums[i] 和 nums[j] 即可，而无须比较 nums[i] * nums[i] 和 nums[j] * nums[j]

若 - nums[i] > nums[j] ，即， nums[i] 的绝对值大于 nums[j] ，则 nums[i] * nums[i] > nums[j] * nums[j] 必然成立
若 - nums[i] <= nums[j] ，则 nums[i] * nums[i] <= nums[j] * nums[j] 必然成立

# LeetCode 27. 移除元素

LeetCode 27. Remove Element

给你一个数组 nums 和一个值 val ，你需要原地移除所有数值等于 val 的元素，并返回移除后数组的新长度。

由于在某些语言中无法改变数组的长度，必须让结果放在数组 nums 的最前面。因此，如果在去除重复元素后还有 k 个元素，那么应该将结果放在 nums 的前 k 个位置，并返回 k 。

不要使用额外的数组空间，你必须仅使用 $O(1)$ 额外空间并原地修改输入数组。

元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

说明:

为什么返回数值是整数，但输出的答案是数组呢？

请注意，输入数组是以「引用」方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。

你可以想象内部操作如下:

int[] nums = [...]; // Input array
int val = ...;      // Value to remove
int[] expectedNums = [...]; // The expected answer with correct length.
                            // It is sorted with no values equaling val.

int k = removeElement(nums, val); // Calls your implementation

assert k == expectedNums.length;
sort(nums, 0, k);           // Sort the first k elements of nums
for (int i = 0; i < actualLength; i++) {
    assert nums[i] == expectedNums[i];
}

示例 1：

输入：nums = [3,2,2,3], val = 3
输出：2, nums = [2,2,_,_]
解释：函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。你不需要考虑数组中超出新长度后面的元素。例如，函数返回的新长度为 2 ，而 nums = [2,2,3,3] 或 nums = [2,2,0,0]，也会被视作正确答案。

示例 2：

输入：nums = [0,1,2,2,3,0,4,2], val = 2
输出：5, nums = [0,1,4,0,3,_,_,_]
解释：函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。注意这五个元素可为任意顺序。你不需要考虑数组中超出新长度后面的元素。

限制:

$0 \le$ nums.length $\le 100$
$0 \le$ nums[i] $\le 50$
$0 \le$ val $\le 100$

# Method 1: 双指针

slow 对应将要被覆盖的位置， fast 对应当前搜索位置，均初始化为 0

fast 右移，并进行如下操作，直到 fast == nums.size() - 1 ：

如果 nums[fast] == val ，跳过该元素
如果 nums[fast] != val ，令 nums[slow] = nums[fast] ，并让 l 右移一位

代码实现：

int removeElement(vector<int>& nums, int val) {
    int n = nums.size();
    int slow = 0;
    for (int fast = 0; fast < n; fast++)
        if (nums[fast] != val) // 对值不为 val 的元素进行移位，值为 val 则跳过
            nums[slow++] = nums[fast];
    return slow;               // slow 即为 新数组的长度
}

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

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

# Method 2: 双指针优化

如果要移除的元素恰好在数组的开头，方法一需要把每一个元素都左移一位

可以定义两个指针，初始时分别指向数组的首尾，向中间移动遍历该序列（题目允许改变元素的顺序）

算法流程：

执行以下循环，直到 left 与 right 重合

判断 left 的元素是否等于 val
- 若是，将 right 指向的元素复制到 left 的位置，然后 right 左移一位
- 若否， left 右移一位

注意这里的 right 指向的元素也有可能是 val ，此时：
可以选择将 val 赋值给 left ，然后 right 左移（在这种情况下，赋值后 left 位置的元素仍为 val ， left 不会移动）
也可以选择跳过该元素，即， right 直接左移

代码实现：

int removeElement(vector<int>& nums, int val) {
    int left = 0, right = nums.size() - 1;
    while (left < right) {
        if (nums[left] == val)
            nums[left] = nums[right--];
        else
            left++;
    }
    return left;
}

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

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

与 Method 1 相比，Method 2 避免了值不为 val 元素的重复赋值操作

# LeetCode 209. 长度最小的子数组

LeetCode 209. Minimum Size Subarray Sum

给定一个含有 n 个正整数的数组和一个正整数 target 。

找出该数组中满足其和 大于或等于 target 的长度最小的 连续子数组 [nums_{l}, nums_{l+1}, ..., nums_{r-1}, nums_{r}] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。

示例 1：

输入：target = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组。

示例 2：

输入：target = 4, nums = [1,4,4]
输出：1

示例 3：

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

提示：

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

进阶：如果你已经实现 $O(n \log{n})$ 时间复杂度的解法，请尝试设计一个 $O(n)$ 时间复杂度的解法。

# Method 1: 暴力法

思路：

对每个下标 i ，找出以 i 为起点、元素和大于等于 target 的子数组的最小长度
从所有的 i 中，找到长度最小值

时间复杂度： $O(n^2)$ ，其中 $n$ 为数组长度

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

# Method 2: 前缀和 + 二分查找

思路：

计算数组 nums 的前缀和，存入新数组 sum ，其中， sum[i] 表示 nums[0] 到 nums[i - 1] 的元素和
初始化所求长度为 ans = INT32_MAX
对每个下标 i
- 利用二分查找算法，找出 sum 数组中大于或等于 sum[i - 1] + target 的最小下标 bound
- 更新满足条件的子数组的最小长度为 ans = min(ans, bound - (i - 1))

长度最小的子数组：前缀和 + 二分查找

时间复杂度： $O(n \log{n})$ ，其中，遍历 i 的时间复杂度为 $O(n)$ ，对每个 i 进行二分查找的时间复杂度为 $(\log{n})$

空间复杂度： $O(n)$ ，额外创建了一个前缀和数组

# Method 3: 滑动窗口

解题思路：

定义指针 left 和 right 分别表示滑动窗口的左端点和右端点，初始化为 0
初始化所求长度为 res = INT32_MAX
迭代，窗口右端点 right 向右移动，直到 right == nums.size()
- 更新窗口内所有元素之和 sum += nums[right]
- 如果 sum >= target ，左端点 left 不断向右移（收缩窗口），直到 sum < target 。在此过程中，须不断更新 sum 和窗口长度 sublength ，并记录满足条件的最小长度 res = (res < sublength) ? res : sublength
判断 res 是否为初值 INT32_MAX ：若是，则返回 0 （不存在满足条件的子数组）；否则，返回 res

代码实现：

int minSubArrayLen(int target, vector<int>& nums) { // 滑动窗口法
    int res = INT32_MAX;    // 所求的最小长度
    int sum = 0;            // 窗口所有元素值之和
    int sublength = 0;      // 窗口长度
    int left = 0;           // 窗口左端
    for (int right = 0; right < nums.size(); right++) { // 遍历窗口右端
        sum += nums[right];
        while (sum >= target) { // 窗口左端点向右移动，直到窗口所有元素值之和小于 target
            sublength = right - left + 1;   // 更新窗口长度
            res = res < sublength ? res : sublength;    // 更新满足条件的最小长度
            sum -= nums[left++];            // 窗口左端向右移动
        }
    }
    return res == INT32_MAX ? 0 : res;      // 若不存在满足条件的子数组，返回 0
}

时间复杂度： $O(n)$ ，指针 left 和 right 最多各移动 $n$ 次， $n$ 为数组长度

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

# 剑指 Offer 03. 数组中重复的数字

剑指 Offer 03

在一个长度为 n 的数组 nums 里，所有数字都在 0 ~ n-1 的范围内，请找出数组中任意一个重复的数字

示例 1：

输入：[2, 3, 1, 0, 2, 5, 3]
输出：2 或 3

提示：

$2 \le$ n $\le 100000$

# stable_sort 函数

int findRepeatNumber(vector<int>& nums) {
    // stable_sort 函数（归并排序的优化实现）
    int n = nums.size();
    stable_sort(nums.begin(), nums.end());

    // 检查是否有重复
    for (int i = 1; i < n; i++) {
        if (nums[i] == nums[i - 1])
            return nums[i];
    }
    return -1;
}

注：这里若采用快速排序或归并排序，将会超出时间限制

# 哈希表

使用集合存储已经遇到的数字，如果遇到的一个数字已经在集合中，则当前的数字是重复数字

算法流程：

初始化 ordered_map 容器，记为 map
遍历数组 nums 中的每个数字 num ：
- 当 num 在 map 中，即， map[num] >= 2 ，直接返回 num
- num 不在 map 中， map[num] 加 1
若遍历结束时未发现重复数字，返回 -1

int findRepeatNumber(vector<int>& nums) {
    unordered_map<int, bool> map;
    for (auto num : nums) {
        if(map[num]) // 若 map[num] = 1，则数字 num 重复
            return num;
        map[num]++;
    }
    return -1;
}

时间复杂度：

$O(n)$ ，遍历数组

空间复杂度：

$O(n)$ ，哈希表占用额外空间

# 原地交换

注意题目说明： 在一个长度为 n 的数组 nums 里的所有数字都在 0 ~ n-1 的范围内 ，因此，可以通过交换操作，建立数组元素索引与值的映射关系

基本思想：遍历数组 nums ，第一次遇到数字 x 时，将其交换至索引 x 处；而当第二次遇到数字 x 时，一定有 nums[x] = x ，得到重复数字

算法流程：

遍历数组 nums ，设索引初始值为 i = 0 ：
- 若 nums[i] = i ：说明此数字已在对应索引位置，无需交换，因此跳过
- 若 nums[nums[i]] = nums[i] ：代表索引 nums[i] 处和索引 i 处的元素值都为 nums[i] ，即找到一组重复值，直接返回值 nums[i]
- 否则：交换索引为 i 和索引为 nums[i] 的两个元素，将此数字交换至对应索引位置
若遍历完毕尚未返回，则返回 -1

代码实现：

int findRepeatNumber(vector<int>& nums) {
    int i = 0, n = nums.size();
    while (i < n) {
        if (nums[i] == i) { // 注意：仅这里进行 i++ ，后续两种情况不进行 i++ 
            i++;
            continue;
        }
        else if (nums[nums[i]] == nums[i])  // 直接返回，无需再操作 i
            return nums[i];
        else                                // 须对 nums[nums[i]] 作进一步的交换操作，将其放至值所对应的索引处，故而此处不进行 i++
            swap(nums[i], nums[nums[i]]);
    }
    return -1;
}

时间复杂度：

$O(N)$ ，遍历数组

空间复杂度：

$O(1)$ ，使用常数复杂度的额外空间

参考：Krahets

# LeetCode 31. 下一个排列

31. Next Permutation

整数数组的一个排列就是将其所有成员以序列或线性顺序排列。

例如，arr = [1,2,3] ，以下这些都可以视作 arr 的排列：[1,2,3]、[1,3,2]、[3,1,2]、[2,3,1] 。

整数数组的下一个排列是指其整数的下一个字典序更大的排列。更正式地，如果数组的所有排列根据其字典顺序从小到大排列在一个容器中，那么数组的下一个排列就是在这个有序容器中排在它后面的那个排列。如果不存在下一个更大的排列，那么这个数组必须重排为字典序最小的排列（即，其元素按升序排列）。

例如，arr = [1,2,3] 的下一个排列是 [1,3,2] 。
类似地，arr = [2,3,1] 的下一个排列是 [3,1,2] 。
arr = [3,2,1] 的下一个排列是 [1,2,3] ，因为 [3,2,1] 不存在一个字典序更大的排列。

给你一个整数数组 nums ，找出 nums 的下一个排列。

必须原地修改，只允许使用额外常数空间。

示例 1：

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

示例 2：

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

示例 3：

输入：nums = [1,1,5]
输出：[1,5,1]

提示：

$1 \le$ nums.length $\le 100$
$0 \le$ nums[i] $\le 100$

# 思路

我们希望找到一个大于字典序更大的排列，并且使得变大的幅度尽可能小，即：

需要将一个左边的「较小数」与一个右边的「较大数」交换，以使得字典序变大
同时，要让这个「较小数」尽量靠右，而「较大数」尽可能小。为此，在完成交换后，需要将「较大数」右边的数按照升序重新排列

以 [4,5,2,6,3,1] 为例：

我们能找到的符合条件的「较小数」与「较大数」的组合为 2 与 3，满足「较小数」尽量靠右、「较大数」尽可能小
当我们完成交换后，序列变为 [4,5,3,6,2,1]，此时我们可以重排「较小数」右边的序列（即，[6,2,1] ），序列变为 [4,5,3,1,2,6]

# Method

算法思路：

从后向前遍历，查找第一个满足 nums[i] < nums[i + 1] 的索引 i ，此时， nums[i] 即为「较小数」，并且，可以证明 [i + 1, n - 1] 必然是下降序列，其中， n 为 nums 的长度
在区间 [i + 1, n - 1] 内从后向前遍历，查找第一个满足 nums[i] < nums[j] 的索引 j ，此时， nums[j] 即为「较大数」
交换 nums[i] 和 nums[j]
反转区间 [i + 1, n - 1] 内的元素，使其变为升序

如果在步骤 1 中无法找到满足条件的 i ，说明当前序列已经是一个字典序最大的排列，直接执行步骤 4 即可得到字典序最小的排列

该方法适用于序列存在重复元素的情况，并且已被 C++ 的标准库函数 next_permutation 采用

代码实现：

void nextPermutation(vector<int>& nums) {
    int i = nums.size() - 2;
    while (i >= 0 && nums[i] >= nums[i + 1]) {
        i--;
    }
    if (i >= 0) {
        int j = nums.size() - 1;
        while (j > i && nums[i] >= nums[j]) {
            j--;
        }
        swap(nums[i], nums[j]);
    }
    reverse(nums.begin() + i + 1, nums.end());
}

时间复杂度： $O(n)$ ，其中 n 为序列 nums 的长度

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

# LeetCode 169. 多数元素

169. Majority Element

给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数大于 ⌊ n / 2 ⌋ 的元素。

你可以假设数组是非空的，并且给定的数组总是存在多数元素。

示例 1：

输入：nums = [3,2,3]
输出：3

示例 2：

输入：nums = [2,2,1,1,1,2,2]
输出：2

提示：

n == nums.length
$1 \le$ n $\le 5 \times 10^4$
$-10^9 \le$ nums[i] $\le 10^9$

进阶： 尝试设计时间复杂度为 $O(n)$ 、空间复杂度为 $O(1)$ 的算法解决此问题。

# Method 1: 哈希表

算法思路：

使用哈希映射（HashMap）来存储每个元素以及出现的次数：对于哈希映射中的每个键值对，键表示一个元素，值表示该元素出现的次数

遍历数组 nums 并统计数组中的每个元素的出现次数，若遇到出现次数大于 ⌊n / 2⌋ 的元素，直接返回

代码实现：

int majorityElement(vector<int>& nums) {
    unordered_map<int, int> hash;
    int temp = nums.size() / 2;
    int ans = 0;
    for (int num : nums) {
        ++hash[num];
        if (hash[num] > temp) {
            ans = num;
            break;
        }
    }
    return ans;
}

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

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

# Method 2: 排序

算法思路：

将数组 nums 中的所有元素按照单调递增（或单调递减）的顺序排序，下标为 $\lfloor \dfrac{n}{2} \rfloor$ 的元素（下标从 0 开始）一定是众数

代码实现：

int majorityElement(vector<int>& nums) {
    sort(nums.begin(), nums.end());
    return nums[nums.size() / 2];
}

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

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

# Method 3: Boyer-Moore 投票法

算法思路：

维护一个候选众数 candidate 和它出现的次数 count，初始时 candidate 可以为任意值，count 为 0

遍历数组 nums 中的所有元素，对于每个元素 x，在判断 x 之前，如果 count 的值为 0，我们先将 x 的值赋予 candidate，随后我们判断 x：

如果 x 与 candidate 相等，那么计数器 count 的值增加 1
如果 x 与 candidate 不等，那么计数器 count 的值减少 1

在遍历完成后，candidate 即为整个数组的众数

代码实现：

int majorityElement(vector<int>& nums) {
    int candidate = 0;
    int count = 0;
    for (int num : nums) {
        if (num == candidate) ++count;
        else {
            --count;
            if (count < 0) {
                candidate = num;
                count = 1;
            }
        }
    }
    return candidate;
}

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

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

参考：leetcode-solution

# LeetCode 238. 除自身以外数组的乘积

238. Product of Array Except Self

给你一个整数数组 nums ，返回数组 answer ，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积。

题目数据保证数组 nums 之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。

请不要使用除法，且在 $O(n)$ 时间复杂度内完成此题。

示例 1：

输入：nums = [1,2,3,4]
输出：[24,12,8,6]

示例 2：

输入：nums = [-1,1,0,-3,3]
输出：[0,0,9,0,0]

提示：

$2 \le$ nums.length $\le 10^5$
$-30 \le$ nums[i] $\le 30$
数组 nums 之中任意元素的全部前缀元素和后缀的乘积都在 32 位整数范围内

进阶：Can you solve the problem in O(1) extra space complexity? (The output array does not count as extra space for space complexity analysis.)

# Method 1: 左右乘积列表

算法思路：

对于索引 i ，分别计算其左侧所有数字（前缀）的乘积和右侧所有数字（后缀）的乘积，将这两个乘积相乘即为 answer [i]

代码实现：

vector<int> productExceptSelf(vector<int>& nums) {
    // 计算索引 i 左侧所有元素的乘积，其中，left[1] 取值为 1
    vector<int> left(nums.size(), 1);  // left[i] 表示区间 [0, i - 1] 内所有元素的乘积
    for (int i = 1; i < nums.size(); ++i) {
        left[i] = left[i - 1] * nums[i - 1];
    }
    // 计算索引 i 右侧所有元素的乘积，其中，right[nums.size() - 1] 取值为 1
    vector<int> right(nums.size(), 1); // right[i] 表示区间 [i + 1, nums.size() - 1] 内所有元素的乘积
    for (int i = nums.size() - 2; i >= 0; --i) {
        right[i] = right[i + 1] * nums[i + 1];
    }
    // 计算 answer[i]
    vector<int> answer(nums.size(), 1);
    for (int i = 0; i < nums.size(); ++i) {
        answer[i] = left[i] * right[i];
    }
    return answer;
}

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

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

# Method 2: 利用答案数组实现 O (1) 空间复杂度

算法思路：

由于输出数组不被视为额外空间，可以利用输出数组来实现 O (1) 空间复杂度：

先将输出数组视为 left 数组（即，先利用 answer [i] 表示索引 i 左侧所有元素的乘积）
然后利用临时变量 tmp 记录索引 i 右侧所有元素的乘积，并维护 answer 数组

代码实现：

vector<int> productExceptSelf(vector<int>& nums) {
    vector<int> answer(nums.size(), 1);
    for (int i = 1; i < nums.size(); ++i) {
        answer[i] = answer[i - 1] * nums[i - 1]; // 索引 i 左侧所有元素的乘积
    }
    int tmp = 1;    // 索引 i 右侧所有元素的乘积
    for (int i = nums.size() - 1; i >= 0; --i) {
        answer[i] = answer[i] * tmp; // 更新 answer 数组
        tmp = tmp * nums[i];         // 更新 tmp
    }
    return answer;
}

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

空间复杂度： $O(1)$ ，不考虑输出数组所占空间

参考：leetcode-solution

# LeetCode 240. 搜索二维矩阵 II

240. Search a 2D Matrix II

编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：

每行的元素从左到右升序排列。
每列的元素从上到下升序排列。

示例 1：

输入：matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 5
输出：true

示例 2：

输入：matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 20
输出：false

提示：

m == matrix.length
n == matrix[i].length
$1 \le$ n , m $\le 300$
$-10^9 \le$ matrix[i][j] $\le 10^9$
$-10^9 \le$ target $\le 10^9$
每行的所有元素从左到右升序排列
每列的所有元素从上到下升序排列

# 思路

注意，在本题中，每行的第一个整数不一定大于前一行的最后一个整数

本题有以下几种解法：

暴力查找：遍历整个矩阵
变形的二分查找：找到矩阵的中心（记作 (midx, midy) ），通过比较 matrix [midx][midy] 与 target 的大小来排除一部分元素（见 LeetCode 提交记录）
- 若 matrix [midx][midy] 等于 target，则已经找到 target，返回 true
- 若 matrix [midx][midy] 小于 target，对于任意 x <= midx 且 y <= midy 的 (x, y)，均有 matrix [x][y] < target，故而可排除所有满足 x <= midx 且 y <= midy 的 (x, y)，然后对剩余区域继续搜索
- 若 matrix [midx][midy] 大于 target，对于任意 x >= midx 且 y >= midy 的 (x, y)，均有 matrix [x][y] > target，故而可排除所有满足 x >= midx 且 y >= midy 的 (x, y)，然后对剩余区域继续搜索
- 令 $m$ 表示当前矩阵的行数， $n$ 表示当前矩阵的列数，则可排除 $\frac{1}{4} m n$ 个元素
逐行二分查找：矩阵的每一行元素都按升序排列，可对每一行使用二分查找（可进一步优化：若当前行的第一个元素大于 target ，则当前行与后续行均不会含有 target，可直接返回 false ；若当前行的最后一个元素小于 target，同样可直接返回 false）
抽象二叉搜素树

# Method: 抽象二叉搜索树

算法思路：

我们可以将二维矩阵中的每个元素视为一个树节点，将整个二维矩阵抽象成一棵以矩阵右上角元素为根的二叉搜索树，此时，每个节点的正左方元素即为它的左子树，正下方元素即为它的右子树

于是，从矩阵 matrix 的右上角（索引为 (0, matrix [0].size () - 1) ）开始搜索，假设当前搜索到的节点为 (x, y)

若 matrix [x][y] 小于 target，则应搜索当前节点的右子树（即，当前矩阵位置的正下方元素），故而执行 ++x 。（也可以这样理解：x 这一行的左边元素都小于 target，应搜索下一行）
若 matrix [x][y] 大于 target，则应搜索当前节点的左子树（即，当前矩阵位置的正左方元素），故而执行 --y 。（也可以这样理解：y 这一列的下边元素都小于 target，应搜索左边一列）

代码实现：

bool searchMatrix(vector<vector<int>>& matrix, int target) {
    int x = 0;
    int y = matrix[0].size() - 1;
    while (x <= matrix.size() - 1 && y >= 0) {
        if (matrix[x][y] == target) return true;
        else if (matrix[x][y] < target) ++x;
        else --y;
    }
    return false;
}

时间复杂度： $O(m + n)$ ，其中， $m$ 和 $n$ 分别是矩阵 matrix 的行数与列数。从 (0, n - 1) 位置开始搜索，x 最多能被增加 m 次，y 最多能被减小 n 次，故而总搜索次数为 $m + n$

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

参考：

leetcode-solution
宫水三叶

# LeetCode 287. 寻找重复数

287. Find the Duplicate Number

给定一个包含 n + 1 个整数的数组 nums ，其数字都在 [1, n] 范围内（包括 1 和 n ），可知至少存在一个重复的整数。

假设 nums 只有 一个重复的整数 ，返回 这个重复的数 。

你设计的解决方案必须 不修改 数组 nums 且只用常量级 $O(1)$ 的额外空间。

示例 1：

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

示例 2：

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

提示：

$1 \le$ n $\le 10^5$
nums.length == n + 1
$1 \le$ nums[i] $\le$ n
nums 中 只有一个整数 出现 两次或多次 ，其余整数均只出现一次

进阶：

如何证明 nums 中至少存在一个重复的数字？
你可以设计一个线性级时间复杂度 $O(n)$ 的解决方案吗？

# Method: 快慢指针

算法思路：

将数组视为一个链表，其中，数组的下标是一个指针，数组的元素也是一个指针，即，指针 0 指向 nums [0]，而 nums [0] 又指向 nums [nums [0]]

对于指针 i ，执行 i = nums [i] 即相当于将指针 i 右移一步，执行 i = nums [nums [i]] 即相当于将指针 i 右移两步

若数组中存在重复数字，则相当于（与数组等价的）链表存在环，重复数字即为环的入口，因此，可按 LeetCode 142. 环形链表 II 进行求解

代码实现：

int findDuplicate(vector<int>& nums) {
    int fast = 0;
    int slow = 0;
    while (true) {
        fast = nums[nums[fast]];
        slow = nums[slow];
        if (fast == slow) {
            int index1 = 0;
            int index2 = slow;
            while (true) {
                index1 = nums[index1];
                index2 = nums[index2];
                if (index1 == index2)
                    return index1; // 注意，重复数字是 index1，而不是 nums[index1]
            }
        }
    }
    return 0;
}

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

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

参考：zjczxz：快慢指针的解释

# LeetCode 448. 找到所有数组中消失的数字

448. Find All Numbers Disappeared in an Array

给你一个含 n 个整数的数组 nums ，其中 nums[i] 在区间 [1, n] 内。请你找出所有在 [1, n] 范围内但没有出现在 nums 中的数字，并以数组的形式返回结果。

示例 1：

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

示例 2：

输入：nums = [1,1]
输出：[2]

提示：

n == nums.length
$1 \le$ n $\le 10^5$
$1 \le$ nums[i] $\le$ n

进阶：你能在不使用额外空间且时间复杂度为 $O(n)$ 的情况下解决这个问题吗？你可以假定返回的数组不算在额外空间内。

# Method: 原地交换

基本思路：

记数组长度为 n，由于数组的索引为 0 至 n - 1、数组元素的取值为 1 至 n，可考虑将数组重新排列，使得数字 x 位于索引为 x - 1 的位置（即，x 应等于 nums [x - 1] ）

遍历重新排列的数组，若位置 x - 1 上的元素不等于 x ，则说明 x 缺失

算法流程：

遍历数组 nums ，实现数组的重新排列：

记当前遍历的位置索引为 i
若 nums [i] 等于 i + 1，说明 nums [i] 处于正确位置，执行 ++i 以处理下一个元素
若 nums [i] 不等于 i + 1，则需将 nums [i] 放到正确位置，即，nums [i] - 1，因此，执行 swap (nums [i], nums [nums [i] - 1]) ，交换位置 i 与位置 nums [i] - 1 上的元素
- 注意，当 nums [i] 等于 nums [nums [i] - 1] 时，不必交换这两个元素
- 由于交换后的 nums [i]（即，交换前的 nums [nums [i] - 1] ）可能不在正确位置，需继续将 nums [i] 交换至正确位置

再次遍历数组 nums ，找出缺失的数字：

记当前遍历的位置索引为 i
若 nums [i] 不等于 i + 1，则说明数字 i + 1 缺失，将其添加到答案数组

代码实现：

vector<int> findDisappearedNumbers(vector<int>& nums) {
    for (int i = 0; i < nums.size(); ++i) {
        while (nums[i] != i + 1 && nums[i] != nums[nums[i] - 1]) {
            swap(nums[i], nums[nums[i] - 1]);
        }
    }
    
    vector<int> ans;
    for (int i = 0; i < nums.size(); ++i) {
        if (nums[i] != i + 1)
            ans.push_back(i + 1);
    }
    
    return ans;
}

复杂度分析：

时间复杂度： $O(n)$ ，其中 $n$ 为数组 nums 的长度。每次交换都可以将一个数字放到正确位置，因此，一共执行 $O(n)$ 次交换

空间复杂度： $O(1)$ ，不考虑答案数组所需空间

# LeetCode 560. 和为 K 的子数组

560. Subarray Sum Equals K

给你一个整数数组 nums 和一个整数 k ，请你统计并返回该数组中和为 k 的连续子数组的个数。

示例 1：

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

示例 2：

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

提示：

$1 \le$ nums.length $\le 2 * 10^4$
$-1000 \le$ nums[i] $\le 1000$
$-10^7 \le$ k $\le 10^7$

# Method: 前缀和

# 算法思路

定义一个前缀和数组 pre ，其中，pre [i] 为数组 nums 中第 0 位至第 i 位所有数的和

建立一个哈希表 unordered_map<int, int> prefix ，将前缀和的值 pre [i] 作为哈希表的 key，将值为 pre [i] 的前缀和的出现次数作为哈希表的 value

于是，以 i 结尾的、和为 k 的连续子数组的个数就是值为 pre [i] - k 的前缀和的出现次数，即， prefix[pre[i] - k]

遍历 i 并且累加 prefix[pre[i] - k] ，即可得到和为 k 的连续子数组的总个数

可用一个变量代替前缀和数组

# 代码实现

int subarraySum(vector<int>& nums, int k) {
    unordered_map<int, int> prefix; // 记录前缀和的出现次数
    prefix[0] = 1; // 初始化（值为 0 的前缀和出现一次）
    int sum = 0;   // 前缀和
    int res = 0;   // 和为 k 的连续子数组
    for (auto num : nums) {
        sum += num;
        res += prefix[sum - k];
        ++prefix[sum];  // 在更新 res 之后才更新 prefix
    }
    return res;
}

# 复杂度分析

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

空间复杂度： $O(n)$ ，在最坏情况下，可能有 n 个不同的哈希表键值，因此需要 $O(n)$ 的空间

# LeetCode 581. 最短无序连续子数组

581. Shortest Unsorted Continuous Subarray

给你一个整数数组 nums ，你需要找出一个 连续子数组 ，如果对这个子数组进行升序排序，那么整个数组都会变为升序排序。

请你找出符合题意的最短子数组，并输出它的长度。

示例 1：

输入：nums = [2,6,4,8,10,9,15]
输出：5
解释：你只需要对 [6, 4, 8, 10, 9] 进行升序排序，那么整个表都会变为升序排序

示例 2：

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

示例 3：

输入：nums = [1]
输出：0

提示：

$1 \le$ nums.length $\le 10^4$
$-10^5 \le$ nums[i] $\le 10^5$

进阶：你可以设计一个时间复杂度为 $O(n)$ 的解决方案吗？

# Method: 寻找左右边界

# 算法思路

从左往右遍历，找到比左边最大值还小的最右侧下标，即为无序子数组的右边界

从右往左遍历，找到比右边最小值还大的最左侧下标，即为无序子树组的左边界

# 代码实现

int findUnsortedSubarray(vector<int>& nums) {
    int right = 0;      // 无序子数组的右边界
    int maxx = INT_MIN; // 左边最大值
    for (int i = 0; i < nums.size(); ++i) { // 寻找小于左边最大值的最右侧下标
        if (nums[i] < maxx) right = i;
        else maxx = nums[i];
    }

    int left = 0;       // 无序子数组的左边界
    int minx = INT_MAX; // 右边最小值
    for (int i = nums.size() - 1; i >= 0; --i) { // 寻找大于右边最大值的最左侧下标
        if (nums[i] > minx) left = i;
        else minx = nums[i];
    }

    if (left == right) return 0;  // 数组 nums 有序，返回 0
    else return right - left + 1; // 最短无序子数组的长度
}

# 复杂度分析

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

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

参考：leetcode-solution

# LeetCode 1523. 在区间范围内统计奇数数目

LeetCode 1523. Count Odd Numbers in an Interval Range

给你两个非负整数 low 和 high 。请你返回 low 和 high 之间（包括二者）奇数的数目。

示例 1：

输入：low = 3, high = 7
输出：3
解释：3 到 7 之间奇数数字为 [3,5,7]

示例 2：

输入：low = 8, high = 10
输出：1
解释：8 到 10 之间奇数数字为 [9]

提示：

$0 \le$ low $\le$ high $\le 10^9$

# Method: 前缀和

暴力枚举 [low,high] 中的所有元素会超出时间限制。

可以使用前缀和思想来解决这个问题，定义 $pre(x)$ 为区间 $[0, x]$ 中奇数的个数，则 $pre(x) = (x + 1)/2$ 。因此 $[low,high]$ 之间的奇数数目为 $pre(high) - pre(low - 1)$

int pre(int x){ // 返回[0,x]之间的奇数数目
    return (x + 1) / 2;
}

int countOdds(int low, int high) { // [low,high]之间的奇数数目=[0,high]之间的奇数数目-[0,low-1]之间的奇数数目
    return pre(high) - pre(low - 1);
}

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

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

# LeetCode 1491. 去掉最低工资和最高工资后的平均工资

LeetCode 1491. Average Salary Excluding the Minimum and Maximum Salary

给你一个整数数组 salary ，数组里每个数都是唯一的，其中 salary[i] 是第 i 个员工的工资。

请你返回去掉最低工资和最高工资以后，剩下员工工资的平均值。

示例 1：

输入：salary = [4000,3000,1000,2000]
输出：2500.00000
解释：最低工资和最高工资分别是 1000 和 4000 。去掉最低工资和最高工资以后的平均工资是 (2000+3000)/2= 2500

示例 2：

输入：salary = [1000,2000,3000]
输出：2000.00000
解释：最低工资和最高工资分别是 1000 和 3000 。去掉最低工资和最高工资以后的平均工资是 (2000)/1= 2000

示例 3：

输入：salary = [6000,5000,4000,3000,2000,1000]
输出：3500.00000

示例 4：

输入：salary = [8000,9000,2000,3000,6000,1000]
输出：4750.00000

提示：

$3 \le$ salary.length $\le 100$
$10^3 \le$ salary[i] $\le 10^6$
salary[i] 是唯一的
与真实值误差在 $10^{-5}$ 以内的结果都将视为正确答案

# Method：前缀和

逐个比较，更新最大值和最小值，并累加求和，最后再减去最大值和最小值。注意，求平均值时，被除数或者除数要转换成 double 型，这样才能保留小数点后的计算结果。

double average(vector<int>& salary) {
    int min = salary[0], max = salary[0], sum = 0;
    for (int i = 0; i < salary.size(); i++)
    {
        if (salary[i] > max) max = salary[i];
        else if (salary[i] < min) min = salary[i];
        sum += salary[i];
    };
    double ans = double(sum - max - min) / (salary.size() - 2); // 注意这里被除数或除数要变成double型
    return ans;

时间复杂度： $O(n)$ ，选取最大值、最小值和求和的过程的时间代价都是 $O(n)$ ，故渐进时间复杂度为 $O(n)$

空间复杂度： $O(1)$ ，这里只用到了常量级别的辅助空间。

数组

# LeetCode 217. 存在重复元素

# Method 1: 排序

# Method 2: 哈希表 set

# Method 3: 哈希表 map

# LeetCode 704. 二分查找

# 思路

# Method 1

# Method 2

# LeetCode 977. 有序数组的平方

# Method 1: 双指针

# Method 2: 双指针

# LeetCode 27. 移除元素

# Method 1: 双指针

# Method 2: 双指针优化

# LeetCode 209. 长度最小的子数组

# Method 1: 暴力法

# Method 2: 前缀和 + 二分查找

# Method 3: 滑动窗口

# 剑指 Offer 03. 数组中重复的数字

# stable_sort 函数

# 哈希表

# 原地交换

# LeetCode 31. 下一个排列

# 思路

# Method

# LeetCode 169. 多数元素

# Method 1: 哈希表

# Method 2: 排序

# Method 3: Boyer-Moore 投票法

# LeetCode 238. 除自身以外数组的乘积

# Method 1: 左右乘积列表

# Method 2: 利用答案数组实现 O (1) 空间复杂度

# LeetCode 240. 搜索二维矩阵 II

# 思路

# Method: 抽象二叉搜索树

# LeetCode 287. 寻找重复数

# Method: 快慢指针

# LeetCode 448. 找到所有数组中消失的数字

# Method: 原地交换

# LeetCode 560. 和为 K 的子数组

# Method: 前缀和

# 算法思路

# 代码实现

# 复杂度分析

# LeetCode 581. 最短无序连续子数组

# Method: 寻找左右边界

# 算法思路

# 代码实现

# 复杂度分析

# LeetCode 1523. 在区间范围内统计奇数数目

# Method: 前缀和

# LeetCode 1491. 去掉最低工资和最高工资后的平均工资

# Method：前缀和

LeetCode - 链表专题

数据结构简介