剑指 Offer 03. 数组中重复的数字">剑指 Offer 03. 数组中重复的数字
剑指 Offer 04. 二维数组中的查找">剑指 Offer 04. 二维数组中的查找
剑指 Offer 11. 旋转数组的最小数字">剑指 Offer 11. 旋转数组的最小数字
剑指 Offer 21. 调整数组顺序使奇数位于偶数前面">(双指针)剑指 Offer 21. 调整数组顺序使奇数位于偶数前面
- 单向扫描法
- 双向扫描法
剑指 Offer 29. 顺时针打印矩阵">剑指 Offer 29. 顺时针打印矩阵
剑指 Offer 39. 数组中出现次数超过一半的数字">剑指 Offer 39. 数组中出现次数超过一半的数字
剑指 Offer 40. 最小的k个数">剑指 Offer 40. 最小的k个数
剑指 Offer 41. 数据流中的中位数">(堆、优先队列)剑指 Offer 41. 数据流中的中位数
面试题50. 第一个只出现一次的字符">(哈希表)面试题50. 第一个只出现一次的字符
剑指 Offer 51. 数组中的逆序对">(分治)剑指 Offer 51. 数组中的逆序对
- 归并排序
剑指 Offer 53 - I. 在排序数组中查找数字 I">剑指 Offer 53 - I. 在排序数组中查找数字 I
- 思路一：暴力查找
- 思路二：二分查找
  - 先找到target再向两边搜索
  - 查找target的左右边界
剑指 Offer 53 - II. 0～n-1中缺失的数字">剑指 Offer 53 - II. 0～n-1中缺失的数字
- 思路一：理论减去实际
- 思路二：二分查找
剑指 Offer 57. 和为s的两个数字">(双指针)剑指 Offer 57. 和为s的两个数字
剑指 Offer 57 - II. 和为s的连续正数序列">(滑动窗口)剑指 Offer 57 - II. 和为s的连续正数序列
剑指 Offer 59 - I. 滑动窗口的最大值">剑指 Offer 59 - I. 滑动窗口的最大值
- 优先队列
剑指 Offer 59 - II. 队列的最大值">剑指 Offer 59 - II. 队列的最大值
剑指 Offer 61. 扑克牌中的顺子">剑指 Offer 61. 扑克牌中的顺子

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

这道题不能把它当简单题来看待

思路一：排序

原地排序，然后遍历，判断前后两个元素是否相等即可
时间复杂度O(nlogn)、较慢

class Solution {
public:
    int findRepeatNumber(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        for (int i = 1; i < nums.size(); i++) {
            if (nums[i] == nums[i - 1])
                return nums[i];
        }
        return -1;
    }
};

思路二：哈希表

使用哈希表或者集合来存储元素，当访问的元素在哈希表中出现两次，则返回该元素
时间复杂度O(n) 空间复杂度O(n)，属于是时间换空间

集合：

class Solution {
public:
    int findRepeatNumber(vector<int>& nums) {
        unordered_set<int> us;
        for (auto num : nums) {
            if (us.count(num)) {
                return num;
            } else {
                us.insert(num);
            }
        }
        return -1; // 如果一定有重复数字的话，程序不会执行到这里
    }
};

哈希表：

class Solution {
public:
    int findRepeatNumber(vector<int>& nums) {
        unordered_map<int, int> um;
        for (auto num : nums) {
            if (um.count(num)) {
                return num;
            } else {
                um[num]++;
            }
        }
        return -1; // 如果一定有重复数字的话，程序不会执行到这里
    }
};

思路三：原地处理O(N)

修改数组

数组长度为n，并且所有数字的范围都在 0 ~ n-1 之间，假设数组完全没有重复，那么数组排序后，值为 i 的元素一定在数组中的下标一定是 i
所以我们可以遍历数组，假设nums[i] = m：

如果 i == m 那么说明 m 处于排序后正确的位置，不作处理
如果 i != m，将 m 与索引为 m 处的元素进行比较：
- 如果 nums[m] == m，说明m重复，返回m
- 如果 nums[m] != m，则交换nums[m]与nums[i]，将m置于排序后正确的位置

循环直到找到重复元素位置

class Solution {
public:
    int findRepeatNumber(vector<int>& nums) {
        // O(n) O(1)
        for (int i = 0; i < nums.size(); i++) {
            while (nums[i] != i) {
                int index = nums[i];
                if (nums[index] == index)
                    return index;
                // swap
                nums[i] = nums[index];
                nums[index] = index;
            }
        }
        return nums[0];
    }
};

虽然两层循环，但是每个数字最多两次交换即可达到正确位置，时间复杂度为O(n)，空间复杂度为O(1)，但会修改原数组

二分查找，不修改原数组

将题目修改为：

数组中共有 n+1 个数字，数字的范围为 1~n 那么必然会有数字重复，在不修改原数组的情况下，找出重复数字，可以使用二分查找
以题目中的例子分析：
数组长度为8，那么数字的范围为1~7，
用中间的数字4将1~7分为两段，1~4 和 5~7，然后统计1~4这四个数字在数组中出现的次数，出现了5次，那么1~4中定有重复数字；
用2将1~4分为两段，1~2和3~4，3、4在数组中共出现3次，那么 3、4中有重复数字
用将3、4分为两部分，3出现两次，返回3
用此方法无法得到所有的重复数字

// 统计范围内数字出现的次数
int countRange(vector<int>& v, int begin, int end) {
    int count = 0;
    for (const auto & num : v ) {
        if (num >= begin && num <= end)
            count++;
    }
    return count;
}
int findDuplication(vector<int>& v) {
    int n = v.size();
    if (n == 0)
        return -1;
    int start = 1, end = n - 1; // 数组中数字的范围为 1 ~ n-1
    while (start <= end) {
        int mid = start + ((end - start) >> 1);
        // 统计左半部分
        int count = countRange(v, start, mid);
        if (start == end) {
            if (count > 1)
                return start;
            else
                break;
        }
        if (count > mid - start + 1) // 数字左边有重复
            end = mid;
        else // 数字右边有重复
            start = mid + 1;
    }
    return -1;
}

按照二分查找的思路，countRange会被调用logn次，每次需要O(n)的时间，因此时间复杂度为O(nlogn)，空间复杂度为O(1)

总结

这道题思路很多，面试时要仔细审题，并认真考虑面试官需求

剑指 Offer 04. 二维数组中的查找

思路一：暴力查找

时间复杂度O(N^2)

思路二：二分查找

每一行进行二分查找，时间复杂度O(NlogN)

思路三：从左上角往下搜索

class Solution {
public:
    bool findNumberIn2DArray(vector<vector<int>>& matrix, int target) {
        if (matrix.size() == 0) return false;
        int n = matrix.size(), m = matrix[0].size();
        int i = 0, j = m - 1;
        while ( i < n && j >= 0) {
            if (matrix[i][j] == target) {
                return true;
            } else if (matrix[i][j] < target) {
                i++;
            } else if (matrix[i][j] > target) {
                j--;
            }
        }
        return false;
    }
};

时间复杂度O(M + N)

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

思路一：暴力查找

class Solution {
public:
    int minArray(vector<int>& numbers) {
        int minN = INT32_MAX;
        for (const auto& num : numbers) {
            minN = min(minN, num);
        }
        return minN;
    }
};

时间复杂度为O(N)

思路二：排序返回第一个元素

class Solution {
public:
    int minArray(vector<int>& numbers) {
        sort(numbers.begin(), numbers.end());
        return numbers[0];
    }
};

时间复杂度为排序的复杂度，快排的话是O(NlogN)

思路三：min_element

class Solution {
public:
    int minArray(vector<int>& numbers) {
        return *min_element(numbers.begin(), numbers.end());
    }
};

思路四：二分查找💦

使用二分法将线性复杂度降为对数复杂度
二分的目的是缩小区间

设左端点为left，右端点为right，中间值为mid （左开右闭）
有序数组经过旋转后，分为两个有序数组，并且左边这个值稍大些，大概是这样的
数组 - 图5
有序数组经过旋转后，最小值的左边元素一定大于等于其右边的元素

假如nums[mid] > nums[right]，最小值一定出现在mid的左边，忽略左边部分
假如nums[mid] < nums[right]，最小值一定出现在mid的右边，忽略右边部分
假如nums[mid] = nums[right]，由于有重复元素的存在，不确定最小值在哪边，为了使最小值依然在区间内，收缩右端点。

当left = right时，返回nums[left]就是最小值
时间复杂度为O(logN)

class Solution {
public:
    int minArray(vector<int>& numbers) {
        int left = 0, right = numbers.size() - 1;
        while (left < right) {
            int mid = left + ((right - left) >> 1);
            if (numbers[mid] > numbers[right]) {
                left = mid + 1;
            } else if (numbers[mid] < numbers[right]) {
                right = mid;
            } else {
                right--;
            }
        }
        return numbers[left];
    }
};

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

这道题考察快速排序的划分操作

单向扫描法

class Solution {
public:
    vector<int> exchange(vector<int>& nums) {
        // 快速排序的划分 partition 单向扫描法 从右向左扫描
        int i = 0, j = nums.size() - 1;
        while (i < j) {
            if (nums[j] % 2 == 0) { // 偶数不用管
                j--;
            } else { // 奇数和i指向的元素交换
                int temp = nums[i];
                nums[i] = nums[j];
                nums[j] = temp;
                i++;
            }
        }
        return nums;
    }
};

双向扫描法

class Solution {
public:
    vector<int> exchange(vector<int>& nums) {
        // 快速排序的划分 partition 双向扫描法
        int i = 0, j = nums.size() - 1;
        while (i < j) {
            while (i < j && nums[i] % 2 != 0) i++; // 找到左数第一个偶数
            while (i < j && nums[j] % 2 == 0) j--; // 找到右数第一个奇数
            // 交换
            if (i < j) {
                int temp = nums[i];
                nums[i] = nums[j];
                nums[j] = temp;
            }
            // 这两行加不加都无所谓
            // i++;
            // j--;
        }
        return nums;
    }
};

剑指 Offer 29. 顺时针打印矩阵

这种比较抽象的问题，可以画图分析，注意循环边界
数组 - 图8

class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        if (matrix.size() == 0 || matrix[0].size() == 0) return {};
        // 记录左上角和右下角的坐标
        int m = matrix.size(), n = matrix[0].size();
        int x1 = 0, y1 = 0; // 左上角
        int x2 = m - 1, y2 = n - 1; // 右下角

        vector<int> res;
        while (x1 <= x2 && y1 <= y2) {
            // 打印第一行
            for (int i = y1; i <= y2; i++) {
                res.push_back(matrix[x1][i]);
            }
            // 打印右边一列
            for (int i = x1 + 1; i <= x2; i++) {
                res.push_back(matrix[i][y2]);
            }
            // 如果最内圈是一行或者一列就不用执行下面的了
            if (x1 < x2 && y1 < y2) {
                // 打印下面一行
                for (int i = y2 - 1; i >= y1; i--) {
                    res.push_back(matrix[x2][i]);
                }
                // 打印左面一列
                for (int i = x2 - 1; i > x1; i--) {
                    res.push_back(matrix[i][y1]);
                }
            }
            x1++;
            y1++;
            x2--;
            y2--;
        }
        return res;
    }
};

class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        if (matrix.size() == 0 || matrix[0].size() == 0) {
            return {};
        }

        int rows = matrix.size(), columns = matrix[0].size();
        vector<int> order;
        int left = 0, right = columns - 1, top = 0, bottom = rows - 1;
        while (left <= right && top <= bottom) {
            for (int column = left; column <= right; column++) {
                order.push_back(matrix[top][column]);
            }
            for (int row = top + 1; row <= bottom; row++) {
                order.push_back(matrix[row][right]);
            }
            if (left < right && top < bottom) {
                for (int column = right - 1; column > left; column--) {
                    order.push_back(matrix[bottom][column]);
                }
                for (int row = bottom; row > top; row--) {
                    order.push_back(matrix[row][left]);
                }
            }
            left++;
            right--;
            top++;
            bottom--;
        }
        return order;
    }
};

剑指 Offer 39. 数组中出现次数超过一半的数字

排序

先排序，再取中间元素，时间复杂度O(nlogn)

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

哈希表

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int n = nums.size();
        unordered_map<int, int> m;
        for (auto num: nums) {
            m[num]++;
            if (m[num] > n / 2)
                return num;
        }
        return -1;
    }
};

时间复杂度O(n)
空间复杂度O(n)

Partition

目标还是寻找排序后位于中间位置的元素，这里简记为中间元素，这里可以使用快速排序的划分思想来处理。
随机选择一个数字，将比它大的放在右边，比它小的放在左边，如果调整后，该数字位于 n / 2的位置，那么该数字就是中间元素，如果位置大于n/2，说明中间元素位于左边，否则位于右边

class Solution {
public:
    int paritition(vector<int>& nums, int left, int right) { // 左闭右开
        int index = left;
        int i = left, j = right - 1;
        int pivot = nums[index];
        while (i < j) {
            while (i < j && nums[j] >= pivot)
                j--;
            if (i < j)
                nums[i++] = nums[j];
            while (i < j && nums[i] < pivot)
                i++;
            if (i < j)
                nums[j--] = nums[i];
        }
        nums[i] = pivot;
        return i;
    }
    int majorityElement(vector<int>& nums) {
        int left = 0, right = nums.size();
        // int mid = left + ((right - left) >> 1);
        int mid = right >> 1;
        int index = paritition(nums, left, right);
        while (index != mid) {
            if (index > mid) {
                right = index - 1;
                index = paritition(nums, left, right);
            } else {
                left = index + 1;
                index = paritition(nums, left, right);
            }
        }
        return nums[index];
    }
};

两两相消，剩下的就是最多的，摩尔投票法

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int count = 0, maj;
        for (auto num : nums) {
            if (count == 0) {
                maj = num;
                count++;
            } else {
                if (num == maj)
                    count++;
                else
                    count--;
            }
        }
        return maj;
    }
};

时间复杂度O(n)
空间复杂度O(1)

剑指 Offer 40. 最小的k个数

排序

class Solution {
public:
    vector<int> getLeastNumbers(vector<int>& arr, int k) {
        sort(arr.begin(), arr.end());
        vector<int> res;
        for (int i = 0; i < k; i++) {
            res.push_back(arr[i]);
        }
        return res;
    }
};

基于partition

与剑指offer39题思路一致，可以基于nums[k]来调整，将比第k个数字大的都置于右边，小的置于左边，然后返回前k个数字

class Solution {
public:
    vector<int> getLeastNumbers(vector<int>& arr, int k) {
        if (k >= arr.size()) return arr;
        return quickSort(arr, k, 0, arr.size() - 1);
    }
private:
    vector<int> quickSort(vector<int>& arr, int k, int l, int r) {
        int i = l, j = r;
        while (i < j) {
            while (i < j && arr[j] >= arr[l]) j--;
            while (i < j && arr[i] <= arr[l]) i++;
            swap(arr[i], arr[j]);
        }
        swap(arr[i], arr[l]);
        if (i > k) return quickSort(arr, k, l, i - 1);
        if (i < k) return quickSort(arr, k, i + 1, r);
        vector<int> res;
        res.assign(arr.begin(), arr.begin() + k);
        return res;
    }
};

堆

适合处理海量数据

(堆、优先队列)剑指 Offer 41. 数据流中的中位数

如果使用数组作为数据结构，那么不断进行插入操作比较耗时
可以使用大顶堆和小顶堆来保存元素，大顶堆保存较小的一半，小顶堆保存较大的一半，可以方便进行插入操作，并且取中位数只需要从堆顶拿就好
这里，元素总数为奇数时，让大顶堆多放一个，取中位数直接取大顶堆堆顶
总数为偶数时，取中位数取二个堆顶元素取平均值

进行插入操作时，

如果两个堆元素数相同，可以先将元素插入小顶堆，然后将小顶堆堆头插入大顶堆，这样可以保证小顶堆始终是较大的一半，大顶堆始终是较小的一半
如果两个堆元素数不同，大顶堆多一个，插入后两堆元素持平，可以先将元素插入大顶堆，然后将大顶堆堆头插入小顶堆，这样可以保证小顶堆始终是较大的一半，大顶堆始终是较小的一半 ```cpp class MedianFinder { public: /* initialize your data structure here. / MedianFinder() {

} void addNum(int num) {
```
  if (pq1.size() == pq2.size()) {
      pq2.push(num);
      pq1.push(pq2.top());
      pq2.pop();
  } else {
      pq1.push(num);
      pq2.push(pq1.top());
      pq1.pop();
  }
```
}

double findMedian() {
```
  return pq1.size() != pq2.size() ? pq1.top() : (pq1.top() + pq2.top()) / 2.0;
```
} priority_queue pq1; // 大顶堆，保存小的一半 priority_queue, greater> pq2; // 小顶堆，保存大的一半 };

/**

Your MedianFinder object will be instantiated and called as such:
MedianFinder* obj = new MedianFinder();
obj->addNum(num);

double param_2 = obj->findMedian(); */

addnum的另一种写法
```cpp
 void addNum(int num) {
     pq1.push(num);
     pq2.push(pq1.top());
     pq1.pop();
     if (pq1.size() < pq2.size()) {
         pq1.push(pq2.top());
         pq2.pop();
     }
 }

(哈希表)面试题50. 第一个只出现一次的字符

class Solution {
public:
    char firstUniqChar(string s) {
        if(s.size() == 0) return ' ';
        int hash[26] = {0};
        for (auto ch : s) {
            hash[ch - 'a']++;
        }
        for (auto ch : s) {
            if (hash[ch - 'a'] == 1)
                return ch;
        }
        return ' ';
    }
};

(分治)剑指 Offer 51. 数组中的逆序对

归并排序

class Solution {
public:
    int mergeSort(vector<int>& nums, vector<int>& tmp, int l, int r) {
        if (l >= r) {
            return 0;
        }

        int mid = (l + r) / 2;
        int inv_count = mergeSort(nums, tmp, l, mid) + mergeSort(nums, tmp, mid + 1, r);
        int i = l, j = mid + 1, pos = l;
        while (i <= mid && j <= r) {
            if (nums[i] <= nums[j]) {
                tmp[pos] = nums[i];
                ++i;
                inv_count += (j - (mid + 1));
            }
            else {
                tmp[pos] = nums[j];
                ++j;
            }
            ++pos;
        }
        for (int k = i; k <= mid; ++k) {
            tmp[pos++] = nums[k];
            inv_count += (j - (mid + 1));
        }
        for (int k = j; k <= r; ++k) {
            tmp[pos++] = nums[k];
        }
        copy(tmp.begin() + l, tmp.begin() + r + 1, nums.begin() + l);
        return inv_count;
    }

    int reversePairs(vector<int>& nums) {
        int n = nums.size();
        vector<int> tmp(n);
        return mergeSort(nums, tmp, 0, n - 1);
    }
};

class Solution {
public:
    int reversePairs(vector<int>& nums) {
        vector<int> tmp(nums.size());
        return merge(0, nums.size() - 1, nums, tmp);

    }
    int merge(int left, int right, vector<int>& nums, vector<int>& tmp) {
        if (left >= right)
            return 0;
        int mid = left + ((right - left) >> 1);
        // 递归
        int res = merge(left, mid, nums, tmp) + merge(mid + 1, right, nums, tmp);
        int i = left, j = mid + 1;
        for (int k = left; k <= right; ++k) {
            tmp[k] = nums[k];
        }
        for (int k = left; k <= right; ++k) {
            if (i == mid + 1) { // 左数组使用完毕
                nums[k] = tmp[j++];
            } else if (j == right + 1 || tmp[i] <= tmp[j]) { // 右数组使用完毕或者左元素小于右元素
                nums[k] = tmp[i++];
            } else { // 当归并操作时，如果左元素大于右元素，需要统计逆序对个数
                nums[k] = tmp[j++];
                res += mid - i + 1; // 如果当前左边元素大于右边,那么左边剩余元素也会比右边的大
                // 因此逆序数对个数增加左边剩余元素个，也就是mid - i + 1
            }
        }
        return res;
    }
};

剑指 Offer 53 - I. 在排序数组中查找数字 I

思路一：暴力查找

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int count = 0;
        for (const auto & num : nums) {
            if (num == target)
                ++count;
        }
        return count;
    }
};

时间复杂度O(N)
空间复杂度O(1)

思路二：二分查找

既然给定的数组是有序的，那么可以使用二分查找来加快查找速度
用二分查找找到的target不一定是第一个，因此需要向左向右继续查找。

先找到target再向两边搜索

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int n = nums.size();
        if (n == 0) 
            return 0;  
        int left = 0, right = n;
        while (left < right) { // 左闭右开
            int mid = left + ((right - left) >> 1);
            if (nums[mid] > target) {
                right = mid; // 右边是开区间
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else { // 找到了target
                int count = 1;
                int l = mid - 1, r = mid + 1; // 向两边查找
                while (l >= 0 && nums[l--] == target) count++;
                while (r < n && nums[r++] == target) count++;
                return count;
            }
        }
        return 0;
    }
};

查找target的左右边界

class Solution {
public:
    int search(vector<int>& nums, int target) {
        if(nums.empty()) return 0;

        int l = 0, r = nums.size() - 1; //二分范围
        // 寻找下界
        while(l < r)                   
        {
            int mid = (l + r) / 2;
            if (nums[mid] >= target) r = mid; // 大于或者等于都要继续向左
            else l = mid + 1;
        }
        if (nums[r] != target) return 0;  //查找失败
        // 查找下界
        int L = r;
        l = 0, r = nums.size() - 1;     //二分范围
        while(l < r)                   //查找元素的结束位置
        {
            int mid = (l + r + 1) / 2;
            if(nums[mid] <= target ) l = mid;
            else r = mid - 1;
        }
        return r - L + 1;
    }
};

STL:

class Solution {
public:
    int search(vector<int>& nums, int target) {
        auto l = lower_bound(nums.begin(), nums.end(), target);
        auto r = upper_bound(nums.begin(), nums.end(), target); 
        return r - l;
    }
};

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

思路一：理论减去实际

求 0 ~ n-1的和，实际的和会比理论和小一个缺少的数字

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int n = nums.size();
        int ans = n * (n + 1) / 2;
        for (const auto & num : nums) {
            ans -= num;
        }
        return ans;
    }
};

时间复杂度为O(N)

思路二：二分查找

数组是有序的，可以使用二分查找
假如某个元素的比它的索引要小了（不可能比索引大），说明在这个元素的前面缺少数字
如果该元素和索引一样大，说明在这个元素的后面缺少数字
我们只需用二分查找来找到第一个比索引小的元素即可，它的下标就是缺失的数字

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int left = 0, right = nums.size();
        while (left < right) { // 左闭右开
            int mid = left + ((right - left) >> 1);
            if (nums[mid] == mid) { // 索引与数字相等，那么左边所有元素索引都与索引相等，找右边
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left; // 最后左右指针相遇的位置，就是第一个下标大于值的元素
    }
};

时间复杂度为O(logN)

(双指针)剑指 Offer 57. 和为s的两个数字

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        if (nums.size() <= 1)
            return {};
        int left = 0, right = nums.size() - 1;
        while (left < right) {
            if (nums[left] + nums[right] > target) {
                right--;
            } else if (nums[left] + nums[right] < target) {
                left++;
            } else {
                return {nums[left], nums[right]};
            }
        }
        return {};
    }
};

(滑动窗口)剑指 Offer 57 - II. 和为s的连续正数序列

class Solution {
public:
    vector<vector<int>> findContinuousSequence(int target) {
        if (target <= 2)
            return {};
        int left = 1, right = 2;
        vector<vector<int>> res;
        list<int> window;
        window.push_back(1);
        window.push_back(2);
        int windowSum = 3;
        int mid = (target + 1) / 2;
        while (right <= mid) {
            if (windowSum == target)
                res.push_back(vector<int>(window.begin(), window.end()));
            while (windowSum > target && left < mid) {
                window.pop_front();
                windowSum -= left++;
                if (windowSum == target)
                res.push_back(vector<int>(window.begin(), window.end()));
            }
            windowSum += ++right;
            window.push_back(right);

        }
        return res;
    }
};

用链表保存窗口元素，再拷贝开销比较大，不如直接构建

class Solution {
public:
    vector<vector<int>> findContinuousSequence(int target) {
        if (target <= 2)
            return {};
        int left = 1, right = 2;
        vector<vector<int>> res;
        vector<int> window;
        int windowSum = 3;
        int mid = (target + 1) / 2;
        while (right <= mid) {
            while (windowSum > target && left < mid) {
                windowSum -= left++;
            }
            if (windowSum == target) {
                window.clear();
                for (int i = left; i <= right; ++i) {
                    window.push_back(i);
                }
                res.push_back(window);
            }
            windowSum += ++right;         
        }
        return res;
    }
};

剑指 Offer 59 - I. 滑动窗口的最大值

优先队列

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        if (nums.size() == 0) return {};
        priority_queue<pair<int, int>> pq;
        for (int i = 0; i < k; ++i) {
            pq.emplace(nums[i], i);
        }
        vector<int> res;
        res.push_back(pq.top().first);
        for (int i = k; i < nums.size(); ++i) {
            pq.emplace(nums[i], i);
            while (pq.top().second <= i - k) {
                pq.pop();
            }
            res.push_back(pq.top().first);
        }
        return res;
    }
};

剑指 Offer 59 - II. 队列的最大值

维护一个单调双端队列，来记录队列的最大值
这个双端队列由队尾到队头为递增
当push操作时，如果一个元素比双端队列队尾的某些元素大的话，这些元素对于队列的最大值就没有影响了，可以将其移除
数组 - 图23
pop_front操作时，如果删除的元素正好是双端队列的队头，那么需要将其从队头删除，否则不做操作

class MaxQueue {
public:
    MaxQueue() {}

    int max_value() {
        if (dq.empty()) return -1;
        return dq.front();
    }

    void push_back(int value) {
        while (!dq.empty() && dq.back() < value) dq.pop_back();
        dq.push_back(value);
        q.push(value);
    }

    int pop_front() {
        if (q.empty()) return -1;
        int ans = q.front();
        if (ans == dq.front()) dq.pop_front();
        q.pop();
        return ans;
    }
    queue<int> q;
    deque<int> dq;
};

剑指 Offer 61. 扑克牌中的顺子

先对排排序，然后统计大小王的数量，然后统计凑成顺子需要补多少张排，如果大小王能够补上，那么返回true

class Solution {
public:
    bool isStraight(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        // 统计0的个数
        int nZero = 0;
        for (int i = 0; i < nums.size() && nums[i] == 0; ++i) {
            ++nZero;
        }
        int small = nZero, big = small + 1;
        int gap = 0;
        while (big < nums.size()) {
            if (nums[small] == nums[big]) // 有对子，不是顺子
                return false;
            gap += nums[big] - nums[small] - 1;
            small = big++;
        }
        return nZero >= gap ? true: false;
    }
};

巧妙的写法

class Solution {
public:
    bool isStraight(vector<int>& nums) {
        int joker = 0;
        sort(nums.begin(), nums.end()); // 数组排序
        for(int i = 0; i < 4; i++) {
            if(nums[i] == 0) joker++; // 统计大小王数量
            else if(nums[i] == nums[i + 1]) return false; // 若有重复，提前返回 false
        }
        return nums[4] - nums[joker] < 5; // 最大牌 - 最小牌 < 5 则可构成顺子
    }
};

数组

思路一：排序

思路二：哈希表

思路三：原地处理O(N)

修改数组

二分查找，不修改原数组

总结

思路一：暴力查找

思路二：二分查找

思路三：从左上角往下搜索

思路一：暴力查找

思路二：排序返回第一个元素

思路三：min_element

思路四：二分查找💦

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

单向扫描法

双向扫描法

排序

哈希表

Partition

两两相消，剩下的就是最多的， 摩尔投票法

排序

基于partition

堆

(堆、优先队列)剑指 Offer 41. 数据流中的中位数

(哈希表)面试题50. 第一个只出现一次的字符

(分治)剑指 Offer 51. 数组中的逆序对

归并排序

思路一：暴力查找

思路二：二分查找

先找到target再向两边搜索

查找target的左右边界

思路一：理论减去实际

思路二：二分查找

(双指针)剑指 Offer 57. 和为s的两个数字

(滑动窗口)剑指 Offer 57 - II. 和为s的连续正数序列

优先队列

两两相消，剩下的就是最多的，摩尔投票法