给你 n 个非负整数 a1，a2，…，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。 说明：你不能倾斜容器，且 n 的值至少为 2。
示例： 输入：[1,8,6,2,5,4,8,3,7] 输出：49
双指针法： 两个指针分别指向左右两端，每次水的容量为两个指针指向的数字中较小值∗指针之间的距离， 每次记录下当次计算得的容量，移动指向数字较小的那个指针，向中间靠拢，计算得容量，若比原来的大则覆盖，否则保持原来的容量。
对于左右指针相等的情况，因为此时左右指针都是“瓶颈”，无论移动哪一个，因为x轴方向的长度变小，移动之后的计算的面积一定减小，故应该两个指针同时移动，而代码实现时任意移动一边的指针即可。
用到algorithm中的min()和max()函数。
class Solution { public: // 双指针法 int maxArea(vector<int>& height) { int left = 0, right = height.size() - 1; int area = 0; while (left < right) { int temp = min(height[left], height[right]) * (right - left); area = max(area, temp); // if (area < min(height[left], height[right]) * (right - left)) // area = min(height[left], height[right]) * (right - left); if (height[left] > height[right]) right--; else if (height[left] <= height[right]) left++; } return area; } };时间复杂度：O(n)，向量中每个元素最多访问一次； 空间复杂度：O(1)，额外使用常数级别的空间。
给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有满足条件且不重复的三元组。 注意：答案中不可以包含重复的三元组。
示例：给定数组 nums = [-1, 0, 1, 2, -1, -4]， 满足要求的三元组集合为： [ [-1, 0, 1], [-1, -1, 2] ]
双指针法 先对数组进行排序，使用algorithm库的sort(nums.begin(), nums.end())，排序begin()到end()-1的数。 为得到不重复的三元组，需要进行相等判断，相等则移动指针，本题中是在边界之后判断数组某个index的值是否等于前一个使用的下标的值。
由于有外层循环first++条件，判断语句中使用continue，不能用first++，否则程序继续执行出现越界错误。
if (first > 0 && nums[first] == nums[first - 1]) continue;第二重循环内部，由于有second++的递增条件，可以不用显示判断左指针移动的情况，只需要在循环内部判断右指针移动的情况，同时进行左右指针位置的检验（left < right）。
while (second < third && nums[second] + nums[third] > target) third--;左右指针边界条件的判断：
if (second == third) break; //相等，说明当前first值无法获取满足条件的三元组，停止当前循环 vector<vector<int>> threeSum(vector<int>& nums) { sort(nums.begin(), nums.end()); vector<vector<int>> ans; int n = nums.size(); for (int first = 0; first < n; ++first) { // skip index that has the same value if (first > 0 && nums[first] == nums[first - 1]) continue; // 不可为first++：下面程序会出现越界错误 int target = -nums[first]; int third = n - 1; for (int second = first + 1; second < n; ++second) { // skip index that has the same value if (second > first + 1 && nums[second] == nums[second - 1]) continue; // 双指针典型用法 while (second < third && nums[second] + nums[third] > target) third--; // 左右指针相等，first指针++ if (second == third) break; if (nums[second] + nums[third] == target) { ans.push_back({nums[first], nums[second], nums[third]}); } } } return ans; }时间复杂度：O(N2)，N为nums数组的长度，对每一个值，在其右侧进行双指针判断（O(N)）； 空间复杂度：O(logN)，额外的排序空间（sort函数）。由于改变了nums数组的值，如果需要另外存储nums数组，则为O(N)。
给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。 你的算法时间复杂度必须是 O(log n) 级别。 如果数组中不存在目标值，返回 [-1, -1]。
示例 1: 输入: nums = [5,7,7,8,8,10], target = 8 输出: [3,4]
示例 2: 输入: nums = [5,7,7,8,8,10], target = 6 输出: [-1,-1]
顺序查找，时间复杂度为O(n)，不满足O(logn)条件。
int left = 0, right = nums.size() - 1; int ptr = 0, flag = 0; if (left == right && nums[0] == target) return { 0, 0 }; //二分法找到target位置 while (left < right) { ptr = (left + right) / 2; if (nums[ptr] > target) { right = ptr - 1; } else if (nums[ptr] < target) { left = ptr + 1; } else { flag = 1; break; } } if (flag == 0) return {-1, -1}; left = ptr; right = ptr; //但判断的时候不满足O(logn)，仍为O(n) while (nums[left] == target) left--; while (nums[right] == target) right++; return { left + 1, right - 1 };要求O(logn)，故考虑二分法。 由于要找出第一个和最后一个位置，在二分位置的值和target相等时，不停止，而是继续移动左右指针，最终找到第一个和最后一个位置。
本次代码实现较多，可以将第一个位置和最后一个位置的获取封装成两个函数。
int left = 0, right = nums.size() - 1; int ptr = 0; while (left <= right) { ptr = (left + right) / 2; if (nums[ptr] > target) { right = ptr - 1; } else if (nums[ptr] < target) { left = ptr + 1; } //==========================关键代码=========================== //==时，不停止循环， //right向左移动，结束时，如果数组nums中存在target，则left指向target的第一个出现的位置 else { right = ptr - 1; } } int first_pos, last_pos; //注意两个条件顺序，nums[left] == target条件不可前置，否则会出错，涉及短路判断 if (left < nums.size() && nums[left] == target) { first_pos = left; } else first_pos = -1; left = 0; right = nums.size() - 1; while (left <= right) { ptr = (left + right) / 2; if (nums[ptr] > target) { right = ptr - 1; } else if (nums[ptr] < target) { left = ptr + 1; } //==========================关键代码=========================== //==时，不停止循环， //left向右移动，结束时，如果数组nums中存在target，则right指向target的最后一个出现的位置 else { left = ptr + 1; } } last_pos = right; if (first_pos == -1) { return { -1, -1 }; } return { first_pos, last_pos };给定一个 n × n 的二维矩阵表示一个图像。 将图像顺时针旋转 90 度。 说明： 你必须在原地旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要使用另一个矩阵来旋转图像。
示例 1: 给定 matrix = [ [1,2,3], [4,5,6], [7,8,9] ], 原地旋转输入矩阵，使其变为: [ [7,4,1], [8,5,2], [9,6,3] ]
示例 2: 给定 matrix = [ [ 5, 1, 9,11], [ 2, 4, 8,10], [13, 3, 6, 7], [15,14,12,16] ], 原地旋转输入矩阵，使其变为: [ [15,13, 2, 5], [14, 3, 4, 1], [12, 6, 8, 9], [16, 7,10,11] ]
一维向量：
vector<int> nums; int r; cin >> r; //说明nums向量的长度大小，才能对向量元素进行赋值操作 nums.resize(r); for (int i = 0; i < r; ++i) { cin >> nums[i]; //nums[i] = i * i... }二维向量：
int row; int column; cout << "请输入数组的行数和列数："; cin >> row >> column; //下面给向量分配存储空间 arr.resize(row); for (int i = 0; i < row; i++) { arr[i].resize(column); }将矩阵的输入和输出封装起来，之后本地调用函数即可进行输入和输出：
void inputMatrix(vector<vector<int>>& matrix) { int r, c; cout << "row: "; cin >> r; cout << "column: "; cin >> c; matrix.resize(r); for (int i = 0; i < r; ++i) { matrix[i].resize(c); //需要先确定向量的长度，之后才能对确定下标的元素操作赋值/输入 //否则只能使用push_back } //输入r*c的矩阵 for (int i = 0; i < r; ++i) { for (int j = 0; j < c; ++j) { cin >> matrix[i][j]; } } } void outputMatrix(vector<vector<int>>& matrix) { //输出r*c的矩阵 for (int i = 0; i < matrix.size(); ++i) { for (int j = 0; j < matrix[0].size(); ++j) { cout << matrix[i][j]; if (j != matrix[0].size() - 1) cout << ", "; else cout << endl; } } }由于要原地翻转，即空间复杂度为O(1)，不可以使用一个与输入矩阵长度相关联的空间存储中间值。
有的题解使用逐层旋转的方法，比较难操作比较繁琐。 为了实现顺时针旋转90°，这里使用矩阵的翻转操作：
先对矩阵上下翻转；对矩阵做转置。 注意：1.2.顺序不调换，若先转置，后面左右翻转操作需要对二维操作，而先上下翻转只需要一位操作即可。 void rotate(vector<vector<int>>& matrix) { int r = matrix.size(), c = matrix[0].size(); //先上下翻转，不左右，因为上下翻转只需要到行坐标，更方便 for (int i = 0; i < r / 2; ++i) { swap(matrix[i], matrix[r - i - 1]); } //再转置 for (int i = 0; i < r; ++i) { for (int j = i; j < c; ++j) { swap(matrix[i][j], matrix[j][i]); } } }给定一个包含 m x n 个元素的矩阵（m 行, n 列），请按照顺时针螺旋顺序，返回矩阵中的所有元素。
示例 1: 输入: [ [ 1, 2, 3 ], [ 4, 5, 6 ], [ 7, 8, 9 ] ] 输出: [1,2,3,6,9,8,7,4,5]
示例 2: 输入: [ [1, 2, 3, 4], [5, 6, 7, 8], [9,10,11,12] ] 输出: [1,2,3,4,8,12,11,10,9,5,6,7]
如图所示，看成一层一层的矩阵。先输出最外层，在逐步输出内层，直到结束。 如何判断边界呢？ 设定4个值即可：left、top、right、bottom，即左上角和右下角的坐标（top，left）和（bottom，right）。
先输出（top，left）到（top，right）的；再输出（top，right）到（bottom，right）；此时需要判断该层内部是否“包着下一层”，是则进入4，否则该层就是一个行向量或者列向量，进行了12之后已经遍历完成；输出（bottom，right - 1）到（bottom，left）；输出（bottom - 1， left）到（top + 1， left）；top++，bottom–，left++，right–，重复上述步骤。注意：边界条件的判断，bottom和right是逐次递减的，top和left是逐次递增的，不要弄错。
vector<int> spiralOrder(vector<vector<int>>& matrix) { //如果矩阵为空，返回一个空向量，向量用｛｝包起来。 if (matrix.size() == 0 || matrix[0].size() == 0) return {}; int row = matrix.size(), col = matrix[0].size(); vector<int> ans; int top = 0, left = 0, bottom = row - 1, right = col - 1; while (top <= bottom && left <= right) { for (int i = left; i <= right; ++i) { ans.push_back(matrix[top][i]); } for (int j = top + 1; j <= bottom; ++j) { ans.push_back(matrix[j][right]); } if (left < right && top < bottom) { for (int ii = right - 1; ii > left; --ii) { ans.push_back(matrix[bottom][ii]); } for (int jj = bottom; jj > top; --jj) { ans.push_back(matrix[jj][left]); } } top++; bottom--; left++; right--; } return ans; }给定一个非负整数数组，你最初位于数组的第一个位置。 数组中的每个元素代表你在该位置可以跳跃的最大长度。 判断你是否能够到达最后一个位置。
示例 1: 输入: [2,3,1,1,4] 输出: true 解释: 我们可以先跳 1 步，从位置 0 到达 位置 1, 然后再从位置 1 跳 3 步到达最后一个位置。 示例 2: 输入: [3,2,1,0,4] 输出: false 解释: 无论怎样，你总会到达索引为 3 的位置。但该位置的最大跳跃长度是 0 ， 所以你永远不可能到达最后一个位置。
使用贪心算法。记录下当前能到达的最远下标farthest，在[当前下标, farthest]里移动，不断更新farthest，若farthest大于最右下标，则返回true，否则若遍历完成，则返回false。
注意：
更新farthest容易漏掉，使用algorithm库的max()函数判断当前farthest和nums[i]+i的较大值；只有下标满足index<farthest条件时，才能更新farthest，否则index为无效值，不参与更新；由于2，可以在遍历循环中添加if条件，满足条件才更新farthest。 bool canJump(vector<int>& nums) { int index = 0, farthest = 0; //遍历数组 for (int i = 0; i < nums.size(); ++i) { //只有满足<farthest条件才更新farthest值 if (i <= farthest) { farthest = max(farthest, nums[i] + i); if (farthest >= nums.size() - 1) return true; } } //遍历结束，说明farthest始终<nums.size()-1，故返回false return false; }给出一个区间的集合，请合并所有重叠的区间。
示例 1: 输入: intervals = [[1,3],[2,6],[8,10],[15,18]] 输出: [[1,6],[8,10],[15,18]] 解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6]. 示例 2: 输入: intervals = [[1,4],[4,5]] 输出: [[1,5]] 解释: 区间 [1,4] 和 [4,5] 可被视为重叠区间。
sort对二维vector的作用：按照二维数组中每一行的第一个元素进行大小排序，该元素大，则该元素所在一维数组就大。
#include <iostream> #include <vector> #include <algorithm> #include <time.h> using namespace std; int main() { srand(time(NULL)); vector<vector<int> > a(10); for (int i = 0; i < 10; i++) for (int j = 0; j < 10; j++) { a[i].push_back(rand() % 100); } for (int i = 0; i < 10; i++) { for (int j = 0; j < 10; j++) { cout << a[i][j] << "\t"; } cout << endl; } cout << "After 2D sorting:" << endl; sort(a.begin(), a.end()); for (int i = 0; i < 10; i++) { for (int j = 0; j < 10; j++) { cout << a[i][j] << "\t"; } cout << endl; } system("pause"); return 0; }结果如下：
贪心算法：
先对区间按上述方法排序，初始时将第一个区间加入到结果数组results数组中，随后按顺序考虑之后的每个区间；
若当前区间的左端点大于results最后一个区间的右端点，则它们不会重合，将当前区间直接加入到results的末尾；
否则它们重合，更新results中最后一个区间的右端点，设为二者的较大值。
对于第一次循环要单独拉出来考虑，这里第一次循环的操作和判断不会重合的情况一致，故将第一次循环的条件和不会重合的条件放在一起。
class Solution { public: // 贪心算法 // 1.先对所有区间按照左端点大小排序； // 2.逐个对比当前区间左端点和results中最后一个区间右端点大小。（初始时将第一个区间直接加入到results） vector<vector<int>> merge(vector<vector<int>>& intervals) { if (intervals.size() == 0) return {}; sort(intervals.begin(), intervals.end()); vector<vector<int>> results; for (int i = 0; i < intervals.size(); ++i) { int L = intervals[i][0], R = intervals[i][1]; if (!results.size() || results.back()[1] < L) { results.push_back({L, R});//添加一个二元数组 } else { results.back()[1] = max(results.back()[1], R); } } return results; } };一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。 问总共有多少条不同的路径？ 输入：m = 3, n = 7 输出：28
给定一个 m x n 的矩阵，如果一个元素为 0，则将其所在行和列的所有元素都设为 0。请使用原地算法。 示例 1: 输入: [ [1,1,1], [1,0,1], [1,1,1] ] 输出: [ [1,0,1], [0,0,0], [1,0,1] ]
示例 2: 输入: [ [0,1,2,0], [3,4,5,2], [1,3,1,5] ] 输出: [ [0,0,0,0], [0,4,5,0], [0,3,1,0] ]
不能直接对原矩阵作置0操作，否则会改变后面要遍历的元素的值，导致错误。
暴力。 最简单的方法。直接复制一个matrix2，遍历原矩阵matrix1，对matrix2操作，需要的额外的空间O(mn)。标记要置0的行和列。 方法1的改进。不存储整个矩阵，存储需要置0的行和列的标志，每行每列都有一个标志位，需要的额外空间O(m+n)。// 不能一边遍历一边更改，后面的数据需要用原本矩阵的值。 // 2.m+n的额外存储空间，标记需要置0的行和列。 void setZeroes(vector<vector<int>>& matrix) { int row = matrix.size(), col = matrix[0].size(); // 初始化为true。 vector<bool> rowReset(row, true); vector<bool> colReset(col, true); for (int i = 0; i < row; ++i) { for (int j = 0; j < col; ++j) { if (matrix[i][j] == 0) { rowReset[i] = 0; colReset[j] = 0; } } } // 修改标记为false的行。 for (int i = 0; i < row; ++i) { if (rowReset[i] == 0) for (int j = 0; j < col; ++j) matrix[i][j] = 0; } // 修改标记为false的列。 for (int i = 0; i < col; ++i) { if (colReset[i] == 0) for (int j = 0; j < row; ++j) matrix[j][i] = 0; } } 方法2的改进：用第一行和第一列来存储标志位，第一行和第一列的标志位用两个变量存储即可。 用第一行和第一列存储标志位，注意修改元素值的时候，先从第二行第二列开始，即先不改动标志位的第一行和第一列，最后在根据两个标记变量修改。// 3.方法2的改进：用第一行和第一列来存储标志位，第一行和第一列的标志位用两个变量存储即可。 void setZeroes(vector<vector<int>>& matrix) { int row = matrix.size(), col = matrix[0].size(); // 初始化为true。 bool firstRow = true, firstCol = true; for (int i = 0; i < col; ++i) { if (matrix[0][i] == 0) { firstRow = false; break; } } for (int i = 0; i < row; ++i) { if (matrix[i][0] == 0) { firstCol = false; break; } } // 从第二行和第二列开始，第一行和第一列若有0，则标志位就是0，不用操作。 for (int i = 1; i < row; ++i) { for (int j = 1; j < col; ++j) { if (matrix[i][j] == 0) { matrix[i][0] = 0; matrix[0][j] = 0; } } } // 置0，注意下标从1开始，否则改变了标记位的值，导致出错。 for (int i = 1; i < row; ++i) { for (int j = 1; j < col; ++j) { if (matrix[i][0] == 0 || matrix[0][j] == 0) { matrix[i][j] = 0; } } } if (firstRow == 0) { for (int i = 0; i < col; ++i) matrix[0][i] = 0; } if (firstCol == 0) { for (int i = 0; i < row; ++i) matrix[i][0] = 0; } }给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。 此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。 进阶： 你可以不使用代码库中的排序函数来解决这道题吗？ 你能想出一个仅使用常数空间的一趟扫描算法吗？
示例 1： 输入：nums = [2,0,2,1,1,0] 输出：[0,0,1,1,2,2] 示例 2： 输入：nums = [2,0,1] 输出：[0,1,2] 示例 3： 输入：nums = [0] 输出：[0] 示例 4： 输入：nums = [1] 输出：[1]
给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。 说明：解集不能包含重复的子集。 示例: 输入: nums = [1,2,3] 输出: [ [3], [1], [2], [1,2,3], [1,3], [2,3], [1,2], [] ]
