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

1. 存在重复元素

2. 二分查找

3. 有序数组的平方

4. 移除元素

5. 长度最小的子数组

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

31. 下一个排列

32. 多数元素

33. 除自身以外数组的乘积

34. 搜索二维矩阵 II

35. 寻找重复数

36. 找到所有数组中消失的数字

37. 和为 K 的子数组

38. 最短无序连续子数组

# 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: 双指针

解题思路：

1. 找出非递减数组 nums 中正负整数的分界线 pos ，假定 nums[pos] <= 0 。当我们将数组 nums 中的数平方后，第 0 位到第 pos 位将单调递减，第 pos + 1 位到第 n − 1 位将单调递增

2. 创建 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: 暴力法

思路：

1. 对每个下标 i ，找出 以 i 为起点、元素和大于等于 target 的子数组的最小长度

2. 从所有的 i 中，找到长度最小值

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

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

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

思路：

1. 计算数组 nums 的前缀和，存入新数组 sum ，其中， sum[i] 表示 nums[0] 到 nums[i - 1] 的元素和

2. 初始化所求长度为 ans = INT32_MAX

3. 对每个下标 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: 滑动窗口

解题思路：

1. 定义指针 left 和 right 分别表示滑动窗口的左端点和右端点，初始化为 0

2. 初始化所求长度为 res = INT32_MAX

3. 迭代，窗口右端点 right 向右移动，直到 right == nums.size()

   • 更新窗口内所有元素之和 sum += nums[right]
   • 如果 sum >= target ，左端点 left 不断向右移（收缩窗口），直到 sum < target 。在此过程中，须不断更新 sum 和窗口长度 sublength ，并记录满足条件的最小长度 res = (res < sublength) ? res : sublength

4. 判断 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;

}

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

# 哈希表

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

算法流程：

1. 初始化 ordered_map 容器，记为 map

2. 遍历数组 nums 中的每个数字 num ：

   • 当 num 在 map 中，即， map[num] >= 2 ，直接返回 num
   • num 不在 map 中， map[num] 加 1

3. 若遍历结束时未发现重复数字，返回 -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 ，得到重复数字

算法流程：

1. 遍历数组 nums ，设索引初始值为 i = 0 ：

   • 若 nums[i] = i ：说明此数字已在对应索引位置，无需交换，因此跳过

   • 若 nums[nums[i]] = nums[i] ：代表索引 nums[i] 处和索引 i 处的元素值都为 nums[i] ，即找到一组重复值，直接返回值 nums[i]

   • 否则：交换索引为 i 和索引为 nums[i] 的两个元素，将此数字交换至对应索引位置

2. 若遍历完毕尚未返回，则返回 -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

算法思路：

1. 从后向前遍历，查找第一个满足 nums[i] < nums[i + 1] 的索引 i ，此时， nums[i] 即为「较小数」，并且，可以证明 [i + 1, n - 1] 必然是下降序列，其中， n 为 nums 的长度

2. 在区间 [i + 1, n - 1] 内从后向前遍历，查找第一个满足 nums[i] < nums[j] 的索引 j ，此时， nums[j] 即为「较大数」

3. 交换 nums[i] 和 nums[j]

4. 反转区间 [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$
• 每行的所有元素从左到右升序排列
• 每列的所有元素从上到下升序排列

# 思路

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

本题有以下几种解法：

1. 暴力查找：遍历整个矩阵

2. 变形的二分查找：找到矩阵的中心（记作 (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$ 个元素

3. 逐行二分查找：矩阵的每一行元素都按升序排列，可对每一行使用二分查找（可进一步优化：若当前行的第一个元素大于 target ，则当前行与后续行均不会含有 target，可直接返回 false ；若当前行的最后一个元素小于 target，同样可直接返回 false）

4. 抽象二叉搜素树

# 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)$ ，这里只用到了常量级别的辅助空间。