通关算法题之 ⌈数组⌋ 下

二分搜索

704. 二分查找

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
1
2

版本一：

//闭区间[left, right]
class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left = 0;
        int right = nums.size() - 1;
        while (left <= right)
        {
            int mid = left + (right - left) / 2;
            if (nums[mid] > target)  right = mid - 1;
            else if (nums[mid] < target)  left = mid + 1;
            else return mid;
        }
        return -1;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

版本二：

//左闭右开区间[left, right)
class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left = 0;
        int right = nums.size();
        while (left < right)
        {
            int mid = left + (right - left) / 2;
            if (nums[mid] > target) right = mid;
            else if (nums[mid] < target) left = mid + 1;
            else return mid;
        }
        return -1;
   }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

🔥while 循环的条件是 <=还是 <？

right = nums.size() - 1相当于两端都闭区间 [left, right]，right = nums.size()相当于左闭右开区间 [left, right)，因为索引大小为 nums.length 是越界的。

什么时候应该停止搜索呢？当然，找到了目标值的时候可以终止：

if(nums[mid] == target) return mid; 
1

但如果没找到，就需要 while 循环终止，然后返回 -1。那 while 循环什么时候应该终止？搜索区间为空的时候应该终止，意味着你没得找了，就等于没找到嘛。

版本一：

while(left <= right) 的终止条件是 left == right + 1，写成区间的形式就是 [right + 1, right]，或者带个具体的数字进去 [3, 2]，可见这时候区间为空，因为没有数字既大于等于 3 又小于等于 2 的吧。所以这时候 while 循环终止是正确的，直接返回 -1 即可。

版本二：

while(left < right) 的终止条件是 left == right，写成区间的形式就是 [right, right)，或者带个具体的数字进去 [2, 2)，这时候区间为空，所以这时候 while 循环终止是正确的，直接返回 -1 即可。

367. 有效的完全平方数

给定一个正整数 num ，编写一个函数，如果 num 是一个完全平方数，则返回 true ，否则返回 false 。

输入：num = 16
输出：true
1
2

可使用二分查找，因为num是正整数，所以若正整数a满足a x a = num，则z一定满足1 < a < num，于是我们可以将1和num作为二分查找搜索区间的初始边界。

class Solution {
public:
    bool isPerfectSquare(int num) {
        int left = 0, right = num;
        while (left <= right) {
            int mid = (right - left) / 2 + left;
            long square = (long) mid * mid;
            if (square < num) {
                left = mid + 1;
            } else if (square > num) {
                right = mid - 1;
            } else {
                return true;
            }
        }
        return false;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

34. 在排序数组中查找元素的第一个和最后一个位置

给定一个按照升序排列的整数数组 nums，和一个目标值 target，找出给定目标值在数组中的开始位置和结束位置。如果数组中不存在目标值 target，返回 [-1, -1]。

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

寻找左侧边界的二分查找：

因为初始化 right = nums.size()，所以决定了「搜索区间」是 [left, right)，所以决定了 while (left < right)，同时也决定了 left = mid + 1 和 right = mid。因为需找到 target 的最左侧索引，所以当 nums[mid] == target 时不要立即返回，而要收紧右侧边界以锁定左侧边界。

寻找右侧边界的二分查找：

因为初始化 right = nums.size()，所以决定了「搜索区间」是 [left, right)，所以决定了 while (left < right)，同时也决定了 left = mid + 1 和 right = mid。因为需找到 target 的最右侧索引，所以当 nums[mid] == target 时不要立即返回，而要收紧左侧边界以锁定右侧边界。又因为收紧左侧边界时必须 left = mid + 1，所以最后无论返回 left 还是 right，必须减一。

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        int left = leftBound(nums, target);
        int right = rightBound(nums, target);
        // [left, right)
        if(left == right) return {-1, -1};
        return {left, right - 1};
    }
	// 找左边界
    int leftBound(vector<int>& nums, int target){
        int left = 0, right = nums.size();
        while(left < right){
            int mid = left + (right - left) / 2;
            if(nums[mid] == target) right = mid;
            else if(nums[mid] > target) right = mid;
            else left = mid + 1;
        }
        return left;
    }
	//找右边界
    int rightBound(vector<int>& nums, int target){
        int left = 0, right = nums.size();
        while(left < right){
            int mid = left + (right - left) / 2;
            if(nums[mid] == target) left = mid + 1;
            else if(nums[mid] > target) right = mid;
            else left = mid + 1;
        }
        return right;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

这道题和剑指 Offer 53 - I. 在排序数组中查找数字 I几乎是一模一样的，只是返回值不一样。剑指 Offer 53 - I. 在排序数组中查找数字 I：统计一个数字在排序数组中出现的次数。

35. 搜索插入位置

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

输入: nums = [1,3,5,6], target = 5
输出: 2
1
2

当目标元素 target 不存在数组 nums 中时，搜索左侧边界的二分搜索的返回值可以做以下几种解读：

返回的这个值是 nums 中大于等于 target 的最小元素索引；
返回的这个值是 target 应该插入在 nums 中的索引位置；
返回的这个值是 nums 中小于 target 的元素个数；

比如在有序数组 nums = [2,3,5,7] 中搜索 target = 4，搜索左边界的二分算法会返回 2，带入上面的说法，都是对的。

所以以上三种解读都是等价的，可以根据具体题目场景灵活运用，显然这里我们需要的是第二种。

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int left = 0, right = nums.size();
        while(left < right){
            int mid = left + (right - left) / 2;
            if(nums[mid] >= target) right = mid;
            else left = mid + 1;
        }
        return left;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12

剑指 Offer 53 - II. 0～n-1中缺失的数字

一个长度为n-1的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围0～n-1之内。在范围0～n-1内的n个数字中有且只有一个数字不在该数组中，请找出这个数字。

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

二分查找，找出第一个不相等于其索引的值。

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int n = nums.size();
        int left = 0, right = n - 1;
        while(left <= right){
            int mid = left + (right - left) / 2;
            if(nums[mid] > mid){
                right = mid - 1;
            }else if (nums[mid] == mid){
                left = mid + 1;
            }
        }
        return left;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

33. 搜索旋转排序数组

整数数组 nums 按升序排列，数组中的值互不相同。在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了旋转，使数组变为 [nums[k], nums[k+1], …, nums[n-1], nums[0], nums[1], …, nums[k-1]]（下标从 0 开始计数）。例如[0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。

给你旋转后的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回 -1 。你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。

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

二分法，主要思路：

（1）原来有序的数组旋转后，从中间分成两部分之后，则一定是一半是有序的，一半是无序的；

（2）根据这个情形，从中间分割后，先判断出哪一半是有序的，然后使用有序的部分，判断当前的目标是否在该有序部分内，若在，则使用该部分接着做分割查找，若不在，则使用另外的部分做分割查找；

（3）主要还是能够想到使用哪些有序的内容来判断目标的存在情形；

class Solution
{
public:
    int search(vector<int> &nums, int target){
        if (nums.empty()) return -1;
        //初始化左右边界
        int left = 0, right = nums.size() - 1;
        while (left <= right){
            int mid = left + (right - left) / 2;
            if (nums[mid] == target){
                return mid;
            }
            //判断哪段是有序的
            if (nums[left] <= nums[mid]){ 
                //左半边是有序的
                //确定目标值是否在有序的部分内
                if (target >= nums[left] && target < nums[mid]){
                    right = mid - 1;
                }else{
                    left = mid + 1;
                }
            }else{ 
                //右半边是有序的
                //判断目标值是否在有序的部分内
                if (target > nums[mid] && target <= nums[right]){
                    left = mid + 1;
                }else{
                    right = mid - 1;
                }
            }
        }
        //若跳出循环，则说明目标值不存在数组内，则返回-1
        return -1;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

剑指 Offer 11. 旋转数组的最小数字

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。给你一个可能存在重复元素值的数组 numbers ，它原来是一个升序排列的数组，并按上述情形进行了一次旋转，请返回旋转数组的最小元素。例如，数组 [3,4,5,1,2] 为 [1,2,3,4,5] 的一次旋转，该数组的最小值为 1。

注意，数组 [a[0], a[1], a[2], …, a[n-1]] 旋转一次的结果为数组 [a[n-1], a[0], a[1], a[2], …, a[n-2]] 。

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

二分法，思路：

step 1：双指针指向旋转后数组的首尾，作为区间端点。

step 2：若是区间中点值大于区间右界值，则最小的数字一定在中点右边。

step 3：若是区间中点值等于区间右界值，则是不容易分辨最小数字在哪半个区间，比如[1,1,1,0,1]，应该逐个缩减右界。

step 4：若是区间中点值小于区间右界值，则最小的数字一定在中点左边。

step 5：通过调整区间最后即可锁定最小值所在。

class Solution {
public:
    int minArray(vector<int>& numbers) {
        int left = 0, right = numbers.size() - 1;
        while(left <= right){
            int mid = left + (right - left) / 2;
            if(numbers[mid] > numbers[right]){//最⼩的数字在mid右边
                left = mid + 1;
            }else if(numbers[mid] == numbers[right]){//⽆法判断，⼀个⼀个试
                right--;
            }else{//最⼩数字要么是mid，要么在mid左边
                right = mid;
            }
        }
        return numbers[left];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

74. 搜索二维矩阵

编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性：每行中的整数从左到右按升序排列，每行的第一个整数大于前一行的最后一个整数。

输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
输出：true
1
2

只要知道二维数组的的行数 m 和列数 n，二维数组的坐标 (i, j) 可以映射成一维的 index = i * n + j；反过来也可以通过一维 index 反解出二维坐标 i = index / n, j = index % n。本题可以实现一个 get 函数把二维数组 matrix 的元素访问抽象成在一维数组中访问元素，然后直接施展最基本的二分搜索即可。

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int m = matrix.size(), n = matrix[0].size();
        // 把二维数组映射到一维
        int left = 0, right = m * n - 1;
        while(left <= right){
            int mid = left + (right - left) / 2;
            int num = get(matrix, mid);
            if(num == target){
                return true;
            }else if(num > target){
                right = mid - 1;
            }else{
                left = mid + 1;
            }
        }
        return false;
    }
    // 通过一维坐标访问二维数组中的元素
    int get(vector<vector<int>>& matrix, int index){
        int m = matrix.size(), n = matrix[0].size();
        // 计算二维中的横纵坐标
        int i = index / n, j = index % n;
        return matrix[i][j];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

378. 有序矩阵中第 K 小的元素（难）

给你一个 n x n 矩阵 matrix ，其中每行和每列元素均按升序排序，找到矩阵中第 k 小的元素。请注意，它是 排序后 的第 k 小元素，而不是第 k 个不同的元素。

输入：matrix = [[1,5,9],[10,11,13],[12,13,15]], k = 8
输出：13
解释：矩阵中的元素为 [1,5,9,10,11,12,13,13,15]，第 8 小元素是 13
1
2
3

二分搜索：

找出二维矩阵中最小的数left，最大的数right，那么第k小的数必定在left~right之间；
mid = left + (right - left) / 2，在二维矩阵中寻找小于等于mid的元素个数count；
若这个count小于k，表明第k小的数在右半部分且不包含mid，即left = mid + 1，right = right，又保证了第k小的数在left~right 之间；
若这个count大于k，表明第k小的数在左半部分且可能包含mid，即left = left，right = mid，又保证了第k小的数在left~right 之间；
因为每次循环中都保证了第k小的数在left-right 之间，当left==right时，第k小的数即被找出，等于right；

注意：这里的left，mid，right是数值，不是索引位置。

class Solution {
public:
    int kthSmallest(vector<vector<int>>& matrix, int k) {
        int m = matrix.size(), n = matrix[0].size();
        int left = matrix[0][0];
        int right = matrix[m - 1][n - 1];
        while (left < right) {
            int mid = left + (right - left) / 2;
            // 找二维矩阵中<= mid的元素总个数
            int count = find(matrix, mid, m, n);
            if (count < k) {
                // 第k小的数在右半部分，且不包含mid
                left = mid + 1;
            } else {
                // 第k小的数在左半部分，可能包含mid
                right = mid;
            }
        }
        return right;
    }

    int find(vector<vector<int>>& matrix, int mid, int m, int n) {
        // 以列为单位找，找到每一列最后一个<=mid的数即知道每一列有多少个数<=mid
        int i = m - 1, j = 0;
        int count = 0;
        while (i >= 0 && j < n) {
            if (matrix[i][j] <= mid) {
                // 第j列有i+1个元素<=mid
                count += i + 1;
                // 这一列找完了，到下一列找
                j++;
            } else {
                // 第j列目前的数大于mid，需要继续在当前列往上找
                i--;
            }
        }
        return count;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

162. 寻找峰值

峰值元素是指其值严格大于左右相邻值的元素。给你一个整数数组 nums，找到峰值元素并返回其索引。数组可能包含多个峰值，在这种情况下，返回 任何一个峰值 所在位置即可。你可以假设 nums[-1] = nums[n] = -∞ 。你必须实现时间复杂度为 O(log n) 的算法来解决此问题。

输入：nums = [1,2,3,1]
输出：2
解释：3 是峰值元素，你的函数应该返回其索引 2。
1
2
3

二分搜索：

根据左右指针计算中间位置 mid，并比较 nums[mid] 与 nums[mid + 1] 的值：如果 nums[mid] 较大，则左侧存在峰值，right = mid；如果 nums[mid + 1] 较大，则右侧存在峰值，left = mid + 1。

class Solution {
public:
    int findPeakElement(vector<int>& nums) {
        int left = 0, right = nums.size() - 1;
        while(left < right){ 
            int mid = left + (right - left) / 2;
            if(nums[mid] > nums[mid + 1]){
                right = mid;
            }else{
                left = mid + 1;
            }
        }
        return left; 
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

1901. 寻找峰值 II

一个 2D 网格中的峰值是指那些严格大于其相邻格子 (上、下、左、右) 的元素。给你一个从 0 开始编号的 m x n 矩阵 mat ，其中任意两个相邻格子的值都不相同。找出任意一个峰值 mat[i][j] 并返回其位置 [i,j] 。你可以假设整个矩阵周边环绕着一圈值为 -1 的格子，要求必须写出时间复杂度为 O(m log(n)) 或 O(n log(m)) 的算法。

输入: mat = [[1,4],[3,2]]
输出: [0,1]
解释: 3 和 4 都是峰值，所以[1,0]和[0,1]都是可接受的答案。
1
2
3

降维使用二分搜索：

class Solution {
public:
    vector<int> findPeakGrid(vector<vector<int>>& mat) {
        int m = mat.size(), n = mat[0].size();
        int left = 0, right = m - 1, maxIndex = 0;
        while(left < right){
            int mid = left + (right - left) / 2;
            maxIndex = getMaxIndex(mat[mid]);
            if(mat[mid][maxIndex] > mat[mid + 1][maxIndex]){
                right = mid;
            }else{
                left = mid + 1;
            }
        }
        maxIndex = getMaxIndex(mat[left]);
        return {left, maxIndex};
        
    }
    
    // 定义：获取数组最大值的索引
    int getMaxIndex(vector<int>& arr){
        int index = 0, max = 0;
        for(int i = 0; i < arr.size(); i++){
            if(arr[i] > max){
                max = arr[i];
                index = i;
            }
        }
        return index;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

双指针

26. 删除有序数组中的重复项

给你一个 升序排列 的数组 nums ，请你原地删除重复出现的元素，使每个元素只出现一次，返回删除后数组的新长度。元素的相对顺序应该保持一致。

示例：

输入：nums = [1,1,2]
输出：2, nums = [1,2,_]
解释：函数应该返回新的长度 2 ，并且原数组 nums 的前两个元素被修改为 1, 2 。不需要考虑数组中超出新长度后面的元素。
1
2
3

让慢指针 slow 走在后面，快指针 fast 走在前面探路，找到一个不重复的元素就告诉 slow 并让 slow 前进一步。这样当 fast 指针遍历完整个数组 nums 后，nums[0..slow] 就是不重复元素。

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        if(!nums.size()) return 0;
        int slow = 0, fast = 0;
        while(fast < nums.size()){
            if(nums[fast] != nums[slow]){
                slow++;
                nums[slow] = nums[fast];
            }
            fast++;
        }
        // 数组长度为 索引 + 1
        return slow + 1;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

27. 移除元素

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

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

题目要求我们把 nums 中所有值为 val 的元素原地删除，依然需要使用快慢指针技巧：如果 fast 遇到值为 val 的元素，则直接跳过，否则就赋值给 slow 指针，并让 slow 前进一步。

注意这里和有序数组去重的解法有一个细节差异，我们这里是先给 nums[slow] 赋值然后再给 slow++，这样可以保证nums[0..slow-1] 是不包含值为 val 的元素的，最后的结果数组长度就是 slow。

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int fast = 0, slow = 0;
        while(fast < nums.size()){
            if(nums[fast] != val){
                nums[slow] = nums[fast];
                slow++;
            }
            fast++;
        }
        return slow;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14

283. 移动零

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

示例：

输入: nums = [0,1,0,3,12]
输出: [1,3,12,0,0]
1
2

可以直接复用 27. 移除元素的解法，先移除所有 0，然后把最后的元素都置为 0，就相当于移动 0 的效果。

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        // 去除nums中的所有0
        int len = remove(nums, 0);
        // 将len之后的所有元素赋值为 0
        while(len < nums.size()){
            nums[len] = 0;
            len++;
        }
    }
	// 定义：在数组nums中移除值为val的元素，返回数组长度
    int remove(vector<int>& nums, int val){
        int fast = 0, slow = 0;
        while(fast < nums.size()){
            if(nums[fast] != val){
                nums[slow] = nums[fast];
                slow++;
            }
            fast++;
        }
        return slow;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

31. 下一个排列

整数数组的一个排列就是将其所有成员以序列或线性顺序排列。例如，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 的下一个排列。必须原地修改，只允许使用额外常数空间。

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

首先从后向前查找第一个顺序对（i，i+1），满足a[i] < a[i+1]。这样「较小数」即为ali]。此时 [ i+1，n）必然是下降序列。
如果找到了顺序对，那么在区间 [i+1，n）中从后向前查找第一个元素j满足a[i] < a[j]。这样「较大数」即为a[j]。
交换a[i]与a[j]，此时区间 [i+1，n）必为降序。我们可以直接使用双指针反转区间 [i+1，n）使其变为升序，而无需对该区间进行排序。

class Solution {
public:
    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 >= 0 && nums[i] >= nums[j]) {
                j--;
            }
            swap(nums[i], nums[j]);
        }
        reverse(nums.begin() + i + 1, nums.end());
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

240. 搜索二维矩阵 II

在一个 n * m 的二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个高效的函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。例如现有矩阵 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。给定 target = 20，返回 false。
1
2
3
4
5
6
7
8
9

不从左上角开始，而是从右上角开始，规定只能向左或向下移动。如果向左移动，元素在减小，如果向下移动，元素在增大，这样就可以根据当前位置的元素和 target 的相对大小来判断应该往哪移动，不断接近从而找到 target 的位置。

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int m = matrix.size(), n = matrix[0].size();
        int i = 0, j = n - 1;
        while(i < m && j >= 0){
            if(matrix[i][j] == target){
                return true;
            }else if(matrix[i][j] > target){
                j--;
            }else{
                i++;
            }
        }
        return false;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

4. 寻找两个正序数组的中位数（难）

给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的中位数 。算法的时间复杂度应该为 O(log (m+n)) 。

输入：nums1 = [1,3], nums2 = [2]
输出：2.00000
解释：合并数组 = [1,2,3] ，中位数 2
1
2
3

本题是要在两个有序数组中找到中位数，故变形为找第 k 个值，对于两个数组的元素是奇数个的，直接找中间位置，对于两个数组元素和是偶数个的，找到中间相邻的两个值之后，求平均即可。

对于第 k 个数，可以先分别在两个数组的前 k/2个数中的数值进行判断，若数组1的第 k/2 个元素小于等于数组2 的第 k/2 个元素，则说明可以排除掉数组1的前 k/2 个元素，反之，排除数组2 的前 k/2 个元素，然后对应的更新两个数组的新的起始位置，及需要判断的新的 k 的位置，既第 k - k/2个，然后重新判断。

需要注意的是，在生成新的数组的起始位置时，要避免越界的情形。

在返回结果时，分为三种情形：一种是数组 1 已经遍历完，则直接在数组 2 中返回对应第 k 个元素；一种是数组 2 已经遍历完，则直接在数组 1 中返回对应的第 k 个元素；最后一种是 k 等于 1 时，只需要返回两个数组中的首位中的较小值即可。

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int totalLength = nums1.size() + nums2.size();
        if (totalLength % 2 == 1) {
            return getKthElement(nums1, nums2, (totalLength + 1) / 2);
        }else {
            return (getKthElement(nums1, nums2, totalLength / 2) 
                    + getKthElement(nums1, nums2, totalLength / 2 + 1)) / 2.0;
        }
    }
    int getKthElement(const vector<int>& nums1, const vector<int>& nums2, int k) {
        int m = nums1.size();
        int n = nums2.size();
        //每次比较时，两个数组的逻辑首地址
        int index1 = 0, index2 = 0;
        while (true) {
            // 边界情况
            if (index1 == m) {
                return nums2[index2 + k - 1];
            }
            if (index2 == n) {
                return nums1[index1 + k - 1];
            }
            if (k == 1) {
                return min(nums1[index1], nums2[index2]);
            }
            // 正常情况
            // 需要比较的两个位置，既变形的二分法的关键，注意避免越界的情形
            int newIndex1 = min(index1 + k / 2 - 1, m - 1);
            int newIndex2 = min(index2 + k / 2 - 1, n - 1);
            int pivot1 = nums1[newIndex1];
            int pivot2 = nums2[newIndex2];
            if (pivot1 <= pivot2) {
                k -= newIndex1 - index1 + 1;
                index1 = newIndex1 + 1;
            }else {
                k -= newIndex2 - index2 + 1;
                index2 = newIndex2 + 1;
            }
        }
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

75. 颜色分类

给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums ，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。必须在不使用库的sort函数的情况下解决这个问题。

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

双指针：使用指针p0来交换0，p2来交换2。p0的初始值为0，而p2的初始值为n - 1。在遍历的过程中，我们需要找出所有的0交换至数组的头部，并且找出所有的2交换至数组的尾部。由于此时其中一个指针p2是从右向左移动的，因此当我们在从左向右遍历整个数组时，如果遍历到的位置超过了p2，那么就可以直接停止遍历了。

从左向右遍历整个数组，如果找到了0，将nums[i]与nums[p0]进行交换，并将p0向后移动一个位置；如果找到了2，那么将nums[i]与nums[p2]进行交换，并将p2向前移动一个位置。

注意：

对于第二种情况，当我们将nums[i]与nums[p2]进行交换之后，新的nums[i]可能仍然是2，也可能是0。然而此时我们已经结束了交换，开始遍历下一个元素nums[i+1]，不会再考虑nums[i]了，这样我们就会得到错误的答案。因此，当我们找到2时，我们需要不断地将其与nums[i] 进行交换，直到新的nums[i]不为2。此时，如果nums[i]为0，那么对应着第一种情况；如果nums[i]为1，那么就不需要进行任何后续的操作。

class Solution {
public:
    void sortColors(vector<int>& nums) {
        int n = nums.size();
        int p0 = 0, p2 = n - 1;
        for (int i = 0; i <= p2; ++i) {
            while (i <= p2 && nums[i] == 2) {
                swap(nums[i], nums[p2]);
                p2--;
            }
            if (nums[i] == 0) {
                swap(nums[i], nums[p0]);
                p0++;
            }
        }
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

剑指 Offer 21. 调整数组顺序使奇数位于偶数前面

输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有奇数在数组的前半部分，所有偶数在数组的后半部分。

输入：nums = [1,2,3,4]
输出：[1,3,2,4] 
注：[3,1,2,4] 也是正确的答案之一。
1
2
3

双指针：

class Solution {
public:
    vector<int> exchange(vector<int>& nums) {
        int left = 0, right = nums.size() - 1;
        while(left < right){
            while(left < right && nums[left] % 2 != 0) left++;
            while(left < right && nums[right] % 2 == 0) right--;
            swap(nums[left], nums[right]);
        }
        return nums;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12

581. 最短无序连续子数组

给你一个整数数组 nums ，你需要找出一个 连续子数组 ，如果对这个子数组进行升序排序，那么整个数组都会变为升序排序。请你找出符合题意的最短子数组，并输出它的长度。

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

可以假设把这个数组分成三段，左段和右段是标准的升序数组，中段数组虽是无序的，但满足最小值大于左段的最大值，最大值小于右段的最小值。找中段的左右边界，我们分别定义为begin 和 end，分两头开始遍历：

从左到右维护一个最大值max，在进入右段之前，那么遍历到的nums[i]都是小于max的，我们要求的end就是遍历中最后一个小于max元素的位置。同理，从右到左维护一个最小值min，在进入左段之前，那么遍历到的nums[i]也都是大于min的，要求的begin也就是最后一个大于min元素的位置。

class Solution {
public:
    int findUnsortedSubarray(vector<int>& nums) {
        int n = nums.size();
        int min = nums[n - 1];
        int max = nums[0];
        int start = 0, end = -1;
        for(int i = 0; i < n; i++){
            // 从左到右维持最大值，寻找右边界end
            if(nums[i] < max){
                end = i;
            }else{
                max = nums[i];
            }
            // 从右到左维持最小值，寻找左边界start
            if(nums[n - i - 1] > min){
                start = n - i - 1;
            }else{
                min = nums[n - i - 1];
            }            
        }
        return end - start + 1;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

NSUM 问题

259. 较小的三数之和

给定一个长度为 n 的整数数组和一个目标值 target，寻找能够使条件 nums[i] + nums[j] + nums[k] < target 成立的三元组 i, j, k 个数（0 <= i < j < k < n）。

输入: nums = [-2,0,1,3], target = 2
输出: 2
解释: 因为一共有两个三元组满足累加和小于 2:
[-2,0,1]
[-2,0,3]
1
2
3
4
5

先对数组进行排序，然后固定第一数，对后面的两个数之和使用正常的双指针进行判断：当满足条件nums[left] + nums[right] < target时，说明right和left之间的数字都可以和left组合满足要求，则满足要求的组合增加为 count += (right - left)，然后将left自增1；若不满足要求，则将right自减 1。

class Solution {
public:
    int threeSumSmaller(vector<int>& nums, int target) {
		sort(nums.begin(), nums.end());
         int count = 0;
		for(int i = 0; i < nums.size() - 2; i++){
            count += twoSumSmaller(nums, target - nums[i], i + 1);
        }
		return count;
	}
    
    int twoSumSmaller(vector<int>& nums, int target, int start){
        int count = 0;
        int lo = start, hi = nums.size() - 1;
        while(lo < hi){
            int sum = nums[lo] + nums[hi];
            if(sum < target){
                count += right - left;
                lo++;
            }else{
                hi--;
            }
        }
        return count;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

16. 最接近的三数之和

给你一个长度为 n 的整数数组 nums 和一个目标值 target。请你从 nums 中选出三个整数，使它们的和与 target 最接近。返回这三个数的和，假定每组输入只存在恰好一个解。

输入：nums = [-1,2,1,-4], target = 1
输出：2
解释：与 target 最接近的和是 2 (-1 + 2 + 1 = 2) 。
1
2
3

一样是先排序，然后固定第一个数，再去 nums[start..] 中寻找最接近 target - delta 的两数之和。

class Solution {
public:
    int threeSumClosest(vector<int>& nums, int target) {
        sort(nums.begin(), nums.end());
        // 记录三数之和与目标值的偏差
        int delta = INT_MAX;
        for(int i = 0; i < nums.size() - 2; i++){
            // 固定 nums[i] 为三数之和中的第一个数，
            // 然后对 nums[i+1..] 搜索接近 target - nums[i] 的两数之和
            int sum = nums[i] + twoSumClosest(nums, target - nums[i], i + 1);
            if(abs(delta) > abs(target - sum)){
                delta = target - sum;
            }
        }
        return target - delta;
    }

    // 在 nums[start..] 搜索最接近 target 的两数之和
    int twoSumClosest(vector<int>& nums, int target, int start){
        int lo = start, hi = nums.size() - 1;
        // 记录两数之和与目标值的偏差
        int delta = INT_MAX;
        while(lo < hi){
            int sum = nums[lo] + nums[hi];
            if(abs(delta) > abs(target - sum)){
                delta = target - sum;
            }
            if(sum < target){
                lo++;
            }else{
                hi--;
            }
        }
        return target - delta;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

167. 两数之和-输入有序数组

给你一个下标从 1 开始的整数数组 numbers ，该数组已按 非递减顺序排列 ，请你从数组中找出满足相加之和等于目标数 target 的两个数。

输入：numbers = [2,7,11,15], target = 9
输出：[1,2]
1
2

只要数组有序，就应该想到双指针技巧。这道题的解法有点类似二分查找，通过调节 left 和 right 就可以调整 sum 的大小：

class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) {
        int left = 0, right = numbers.size() - 1;
        while(left < right){
            int sum = numbers[left] + numbers[right];
            if(sum == target){
                return {left + 1, right + 1}; 
            }else if(sum < target){
                left++;
            }else{
                right--;
            }
        }
        return {};
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

1. 两数之和

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那两个整数，并返回它们的数组下标。

输入：nums = [2,7,11,15], target = 9
输出：[0,1]
1
2

若要求返回数组元素，则可以可将数组排序后使用双指针：

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        sort(nums.begin(), nums.end());
        int left = 0, right = nums.size() - 1;
        while(left < right){
            int sum = nums[left] + nums[right];
            if(sum == target){
                return {nums[left], nums[right]};
            }else if(sum < target){
                left++;
            }else{
                right--;
            }
        }
        return {};
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

若要求返回数组元素的索引，则无法使用上述的双指针，因为排序后数组元素的索引有变动，可使用哈希表：

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> map;
        for(int i = 0; i < nums.size(); i++){
            auto it = map.find(target - nums[i]);
            if(it != map.end()) return {it->second, i};
            map[nums[i]] = i;
        }
        return {};
    }
};
1
2
3
4
5
6
7
8
9
10
11
12

魔改题目：

nums 中可能有多对元素之和都等于 target，请你的算法返回所有和为 target 的元素对，其中不能出现重复。

vector<vector<int>> twoSumTarget(vector<int>& nums, int target) {
    // nums 数组必须有序
    sort(nums.begin(), nums.end());
    int lo = 0, hi = nums.size() - 1;
    vector<vector<int>> res;
    while (lo < hi) {
        int sum = nums[lo] + nums[hi];
        // 记录索引 lo 和 hi 最初对应的值
        int left = nums[lo], right = nums[hi];
        if (sum < target) {
            while (lo < hi && nums[lo] == left) lo++;
        } else if (sum > target) {
            while (lo < hi && nums[hi] == right) hi--;
        } else {
            res.push_back({left, right});
            // 跳过所有重复的元素
            while (lo < hi && nums[lo] == left) lo++;
            while (lo < hi && nums[hi] == right) hi--;
        }
    }
    return res;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

15. 三数之和

给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。

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

这个问题怎么解决呢？很简单，穷举呗。现在我们想找和为 target 的三个数字，那么对于第一个数字，可能是什么？nums 中的每一个元素 nums[i] 都有可能！

那么，确定了第一个数字之后，剩下的两个数字可以是什么呢？其实就是和为 target - nums[i] 的两个数字呗，那不就是 twoSum 函数解决的问题么🤔。

关键点在于，不能让第一个数重复，至于后面的两个数，我们复用的 twoSum 函数会保证它们不重复。所以代码中必须用一个 while 循环来保证 3Sum 中第一个元素不重复。

class Solution {
public:

    /* 计算数组 nums 中所有和为 target 的三元组 */
    vector<vector<int>> threeSum(vector<int>& nums) {
        // 数组得排个序
        sort(nums.begin(), nums.end());
        int n = nums.size();
        vector<vector<int>> res;
        // 穷举 threeSum 的第一个数
        for (int i = 0; i < n; i++) {
            // 对 target - nums[i] 计算 twoSum
            vector<vector<int>> tuples = twoSumTarget(nums, i + 1, - nums[i]);
            // 如果存在满足条件的二元组，再加上 nums[i] 就是结果三元组
            for (vector<int>& tuple : tuples) {
                tuple.push_back(nums[i]);
                res.push_back(tuple);
            }
            // 跳过第一个数字重复的情况，否则会出现重复结果
            while (i < n - 1 && nums[i] == nums[i + 1]) i++;
        }
        return res;
    }
    vector<vector<int>> twoSumTarget(vector<int>& nums, int start, int target) {
        // nums 数组必须有序
        sort(nums.begin(), nums.end());
        int lo = start, hi = nums.size() - 1;
        vector<vector<int>> res;
        while (lo < hi) {
            int sum = nums[lo] + nums[hi];
            // 记录索引 lo 和 hi 最初对应的值
            int left = nums[lo], right = nums[hi];
            if (sum < target) {
                while (lo < hi && nums[lo] == left) lo++;
            } else if (sum > target) {
                while (lo < hi && nums[hi] == right) hi--;
            } else {
                res.push_back({left, right});
                // 跳过所有重复的元素
                while (lo < hi && nums[lo] == left) lo++;
                while (lo < hi && nums[hi] == right) hi--;
            }
        }
        return res;
    }    
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

代码优化一下：

再比如 LeetCode 的 3Sum 问题，找 target == 0 的三元组：

vector<vector<int>> threeSum(vector<int>& nums) {
    sort(nums.begin(), nums.end());
    // n 为 3，从 nums[0] 开始计算和为 0 的三元组
    return nSumTarget(nums, 3, 0, 0);        
}
1
2
3
4
5

nSumTarget函数实现见下一题。

18. 四数之和

给你一个由 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

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

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

都到这份上了，4Sum 完全就可以用相同的思路：穷举第一个数字，然后调用 3Sum 函数计算剩下三个数，最后组合出和为 target 的四元组。总结 nSum 函数：

/* 注意：调用这个函数之前一定要先给 nums 排序 */
// n为整数个数，start为双指针初始值，target为目标值
vector<vector<int>> nSumTarget(vector<int>& nums, int n, int start, int target) {
    int size = nums.size();
    vector<vector<int>> res;
    // 至少是 2Sum，且数组大小不应该小于 n
    if (n < 2 || size < n) return res;
    // 2Sum 是 base case
    if (n == 2) {
        // 双指针那一套操作
        int lo = start, hi = size - 1;
        while (lo < hi) {
            int left = nums[lo], right = nums[hi];
            int sum = left + right;                
            if (sum < target) {
                while (lo < hi && nums[lo] == left) lo++;
            } else if (sum > target) {
                while (lo < hi && nums[hi] == right) hi--;
            } else {
                res.push_back({left, right});
                while (lo < hi && nums[lo] == left) lo++;
                while (lo < hi && nums[hi] == right) hi--;
            }
        }
    } else {
        // n > 2 时，递归计算 (n-1)Sum 的结果
        for (int i = start; i < size; i++) {
            vector<vector<int>> sub = nSumTarget(nums, n - 1, i + 1, target - nums[i]);
            for (vector<int>& arr : sub) {
                // (n-1)Sum 加上 nums[i] 就是 nSum
                arr.push_back(nums[i]);
                res.push_back(arr);
            }
            while (i < size - 1 && nums[i] == nums[i + 1]) i++;
        }
    }
    return res;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

实际上就是把之前的题目解法合并起来了，n == 2 时是 twoSum 的双指针解法，n > 2 时就是穷举第一个数字，然后递归调用计算 (n-1)Sum，组装答案。

需要注意的是，调用这个 nSum 函数之前一定要先给 nums 数组排序，因为 nSum 是一个递归函数，如果在 nSum 函数里调用排序函数，那么每次递归都会进行没有必要的排序，效率会非常低。

比如说现在我们写 LeetCode 上的 4Sum 问题：

vector<vector<int>> fourSum(vector<int>& nums, int target) {
    sort(nums.begin(), nums.end());
    // n 为 4，从 nums[0] 开始计算和为 target 的四元组
    return nSumTarget(nums, 4, 0, target);
}
1
2
3
4
5

那么，如果让你计算 100Sum 问题，直接调用这个函数就完事儿了。

相关阅读:
Jmeter全流程性能测试实战
 创意写作类国际竞赛有哪些？
0基础学习PyFlink——使用PyFlink的SQL进行字数统计
 计算机网络八股
 Kafka系列之：深入理解Kafka Connect REST API
pyenv fails with : ModuleNotFoundError: No module named ‘_ctypes‘ error
uniapp:tabBar点击后设置动画效果
 虚拟化与元宇宙：人类文明演化的奇点与治理
 新库上线 | CnOpenData信息传输、软件和信息技术服务业工商注册企业基本信息数据
 Java反射技术
原文地址：https://blog.csdn.net/weixin_42461320/article/details/128003488