给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。
示例:
给定 nums = [2, 7, 11, 15], target = 9 因为 nums[0] + nums[1] = 2 + 7 = 9 所以返回 [0, 1]维护一个hash表，边遍历数组边存储值到hash表中，当遍历到nums[i]时，如果hash[target - nums[i]] > 0，那么就找到了符合条件的两个值
时间复杂度：O(n)空间复杂度：O(n)C++代码
class Solution { public: vector<int> twoSum(vector<int>& nums, int target) { vector<int> res(2,-1); unordered_map<int, int> hash; for(int i = 0; i < nums.size(); i++) { if(hash.count(target - nums[i]) != 0) { res[0] = hash[target - nums[i]]; res[1] = i; break; } hash[nums[i]] = i; } return res; } };给定两个数组，编写一个函数来计算它们的交集。
示例 1:
输入: nums1 = [1,2,2,1], nums2 = [2,2] 输出: [2]示例 2:
输入: nums1 = [4,9,5], nums2 = [9,4,9,8,4] 输出: [9,4]说明:
输出结果中的每个元素一定是唯一的。
我们可以不考虑输出结果的顺序。
方法1
将数组nums1的元素放入一个set中，然后遍历nums2的元素nums2[i]，判断它是否在set中，如果在set中，则说明这个元素是交集的部分，将它加入结果中。
设nums1的大小为m，数组nums2的大小为n
时间复杂度：O(m + n)空间复杂度：O(m)C++代码
class Solution { public: vector<int> intersection(vector<int>& nums1, vector<int>& nums2) { if(nums1.empty() || nums2.empty()) return vector<int>(); unordered_set<int> st; for(auto a : nums1) st.insert(a); vector<int> res; for(int a : nums2) { if(st.count(a) > 0) { res.push_back(a); st.erase(a); } } return res; } }; 方法2：排序 +双指针先将nums1和nums2排序(从小到大排序)，维护一个set存放交集元素，定义两个指针p1和p2分别从nums1和nums2出发，处理情况如下：
如果nums1[p1] == nums2[p2]，则将numns[p1]放入set，同时++p1,++p2；否则，nums1[p1] < nums2[p2] ? ++p1 : ++p2。直到p1或p2到达数组尾部。
最后将set中的元素放入结果数组中即可。
设nums1的大小为m，数组nums2的大小为n
时间复杂度：O(m log m + n log n)空间复杂度：O(max(m,n))C++代码
class Solution { public: vector<int> intersection(vector<int>& nums1, vector<int>& nums2) { sort(nums1.begin(),nums1.end()); sort(nums2.begin(),nums2.end()); vector<int> res; set<int> st; int p1 = 0,p2 = 0; while(p1 < nums1.size() && p2 < nums2.size()) { if(nums1[p1] == nums2[p2]) { st.insert(nums1[p1]); ++p1; ++p2; } else{ nums1[p1] < nums2[p2] ? ++p1 : ++p2; } } for(auto a : st) res.push_back(a); return res; } }; 方法3现将nums1从小到大排序，遍历数组nums2的每一个元素nums2[i]，同时在nums1中二分查找nums2[i]，如果能找到nums2[i]，则将它加入set中；否则，跳过。最后，将set中的元素放入结果数组即可。
设nums1的大小为m，数组nums2的大小为n
时间复杂度：O((m + n) log m)空间复杂度：O(min(m,n))C++代码
class Solution { public: bool binarySearch(const vector<int>& vec,int target) { int l = 0,r = vec.size() - 1; while(l <= r) { int m = (l + r) / 2; if(vec[m] < target) l = m+1; else if(vec[m] > target) r = m-1; else return true; } return false; } vector<int> intersection(vector<int>& nums1, vector<int>& nums2) { sort(nums1.begin(),nums1.end()); set<int> st; vector<int> res; for(auto a : nums2) { if(binarySearch(nums1,a)) st.insert(a); } for(auto a : st) res.push_back(a); return res; } };给定两个数组，编写一个函数来计算它们的交集。
示例 1:
输入: nums1 = [1,2,2,1], nums2 = [2,2] 输出: [2,2]示例 2:
输入: nums1 = [4,9,5], nums2 = [9,4,9,8,4] 输出: [4,9]说明：
输出结果中每个元素出现的次数，应与元素在两个数组中出现的次数一致。我们可以不考虑输出结果的顺序。进阶:
如果给定的数组已经排好序呢？你将如何优化你的算法？
如果 nums1 的大小比 nums2 小很多，哪种方法更优？
如果 nums2 的元素存储在磁盘上，磁盘内存是有限的，并且你不能一次加载所有的元素到内存中，你该怎么办？
方法1
用unordered_map（无序哈希表）来建立nums1中字符和其出现个数之间的映射, 然后遍历nums2数组，如果当前字符在哈希表中的个数大于0，则将此字符加入结果中，然后哈希表的对应值自减1。
设nums1的大小为m，数组nums2的大小为n
时间复杂度：O(m + n)空间复杂度：O(max(m,n))C++代码
class Solution { public: vector<int> intersect(vector<int>& nums1, vector<int>& nums2) { vector<int> res; unordered_map<int,int> mp; for(auto a : nums1) ++mp[a]; for(auto b : nums2) { if(mp[b] > 0) { res.push_back(b); --mp[b]; } } return res; } };优化空间：哈希表统计两数组中长度较小的那个数组的元素个数。
时间复杂度：O(m + n)空间复杂度：O(min(m,n))C++代码
class Solution { public: vector<int> intersect(vector<int>& nums1, vector<int>& nums2) { vector<int> res; unordered_map<int,int> mp; if(nums1.size() > nums2.size()) { //长度较小的数组拷贝到临时数组 vector<int> tmp(nums2); nums2 = nums1; nums1 = tmp; } for(auto a : nums1) ++mp[a]; for(auto b : nums2) { if(mp[b] > 0) { res.push_back(b); --mp[b]; } } return res; } }; 方法2先将nums1和nums2排序(从小到大排序)，定义两个指针p1和p2分别从nums1和nums2出发，处理情况如下：
如果nums1[p1] == nums2[p2]，则将numns[p1]放入结果，同时++p1,++p2；否则，nums1[p1] < nums2[p2] ? ++p1 : ++p2。直到p1或p2到达数组尾部。
设nums1的大小为m，数组nums2的大小为n
时间复杂度：O(m log m + n log n)空间复杂度：O(max(m,n))C++代码
class Solution { public: vector<int> intersect(vector<int>& nums1, vector<int>& nums2) { sort(nums1.begin(),nums1.end()); sort(nums2.begin(),nums2.end()); vector<int> res; int p1 = 0,p2 = 0; while(p1 < nums1.size() && p2 < nums2.size()) { if(nums1[p1] == nums2[p2]) { res.push_back(nums1[p1]); ++p1; ++p2; } else{ nums1[p1] < nums2[p2] ? ++p1 : ++p2; } } return res; } };给定一个整数数组，判断是否存在重复元素。
如果任何值在数组中出现至少两次，函数返回 true。如果数组中每个元素都不相同，则返回 false。
示例 1:
输入: [1,2,3,1] 输出: true示例 2:
输入: [1,2,3,4] 输出: false利用unordered_set无序集合，遍历数组的时候将元素放入集合中，找出已经在集合中出现的元素就是重复的元素
时间复杂度：O(n)空间复杂度：O(n)C++代码
class Solution { public: bool containsDuplicate(vector<int>& nums) { if(nums.empty()) return false; int len=nums.size(); unordered_set<int> st; for(auto a:nums) { if(st.find(a) != st.end()) return true; else st.insert(a); } return false; } };给定一个大小为 n 的数组，找到其中的众数。众数是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的，并且给定的数组总是存在众数。
示例 1：
输入：[3,2,3] 输出：3示例 2：
输入：[2,2,1,1,1,2,2] 输出：2方法1：哈希表
基于原数组建立哈希表，key为元素，value为元素个数，找出value > len/2的元素就是众数
时间复杂度：O(n)空间复杂度：O(n)C++代码
class Solution { public: int majorityElement(vector<int>& nums) { unordered_map<int,int> mp; int len = nums.size(); int res = INT_MIN; for(auto a : nums) { mp[a]++; if(mp[a] > len/2) { res = a; break; } } return res; } };方法2：摩尔投票法
参见博客
时间复杂度：O(n)空间复杂度：O(1)C++代码
class Solution { public: int majorityElement(vector<int>& nums) { int cnt = 0; int res = 0; for(int i=0;i<nums.size();i++) { if(cnt == 0) { cnt++; res = nums[i]; } else if(nums[i] == res) cnt++; else cnt--; } return res; } };判断一个 9x9 的数独是否有效。只需要根据以下规则，验证已经填入的数字是否有效即可。
数字 1-9 在每一行只能出现一次。数字 1-9 在每一列只能出现一次。数字 1-9 在每一个以粗实线分隔的 3x3 宫格内只能出现一次。上图是一个部分填充的有效的数独。
数独部分空格内已填入了数字，空白格用 '.' 表示。
示例 1:
输入: [ ["5","3",".",".","7",".",".",".","."], ["6",".",".","1","9","5",".",".","."], [".","9","8",".",".",".",".","6","."], ["8",".",".",".","6",".",".",".","3"], ["4",".",".","8",".","3",".",".","1"], ["7",".",".",".","2",".",".",".","6"], [".","6",".",".",".",".","2","8","."], [".",".",".","4","1","9",".",".","5"], [".",".",".",".","8",".",".","7","9"] ] 输出: true示例 2:
输入: [ ["8","3",".",".","7",".",".",".","."], ["6",".",".","1","9","5",".",".","."], [".","9","8",".",".",".",".","6","."], ["8",".",".",".","6",".",".",".","3"], ["4",".",".","8",".","3",".",".","1"], ["7",".",".",".","2",".",".",".","6"], [".","6",".",".",".",".","2","8","."], [".",".",".","4","1","9",".",".","5"], [".",".",".",".","8",".",".","7","9"] ] 输出: false 解释: 除了第一行的第一个数字从 5 改为 8 以外，空格内其他数字均与 示例1 相同。 但由于位于左上角的 3x3 宫内有两个 8 存在, 因此这个数独是无效的。说明:
一个有效的数独（部分已被填充）不一定是可解的。只需要根据以上规则，验证已经填入的数字是否有效即可。给定数独序列只包含数字 1-9 和字符 '.' 。给定数独永远是 9x9 形式的。解答
要判断是否出现重复元素，只需要遍历的时候用哈希表记录每一个字符ch(介于'1'~'9'之间)出现的次数，当字符再次出现的时候判断ch在哈希表中的次数是否大于0，就可以判断是否出现重复的字符。由于在每一行、每一列和每一个3x3宫格内都不能出现重复的字符，那么需要以逐行、逐列和逐个3x3宫格的方式分别遍历，同时利用哈希表记录并判断，便能得出结果。
时间复杂度：O(9x9) = O(1)空间复杂度：O(9) = O(1)C++代码
class Solution { public: bool isValidSudoku(vector<vector<char>>& board) { unordered_map<char,int> mp; int row = board.size(); int col = board[0].size(); for(int i=0;i<row;i++) { for(int j=0;j<col;j++) { int ch = board[i][j]; if(ch != '.') { mp[ch]++; if(mp[ch] > 1) return false; } } mp.clear(); } for(int i=0;i<col;i++) { for(int j=0;j<row;j++) { char ch = board[j][i]; if(ch != '.') { mp[ch]++; if(mp[ch] > 1) return false; } } mp.clear(); } for(int i=0;i<row;i+=3) { for(int j=0;j<col;j+=3) { for(int x=i;x<i+3;x++) for(int y=j;y<j+3;y++) { char ch=board[x][y]; if(ch != '.') { mp[ch]++; if(mp[ch] > 1) return false; } } mp.clear(); } } return true; } };给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？找出所有满足条件且不重复的三元组。
注意：答案中不可以包含重复的三元组。
例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4]， 满足要求的三元组集合为： [ [-1, 0, 1], [-1, -1, 2] ]对整个数组排序，先遍历数组取三数中的第一个数nums[i]，注意num[i]只到数组的倒数第三个元素，然后剩下两个数需要满足条件target = 0 - nums[i],这两个数在数组中num[i]后面部分，维持两个双指针l和r，令tmp = nums[l] + nums[r]，处理情况如下：
如果tmp < target，则l右移一步；如果tmp > target，则r左移一步；否则，满足条件，添加两个数到结果数组中，同时将l和r分别右移和左移到下一个不重复的元素处。注意：遍历数组的时候取第一个数的时候过滤重复元素，可以提高查找效率
时间复杂度：O(n2)空间复杂度：O(1) class Solution { public: vector<vector<int>> threeSum(vector<int>& nums) { int len = nums.size(); if(len < 3) return vector<vector<int>>(); sort(nums.begin(),nums.end()); vector<vector<int>> res; for(int i=0;i<len-2;i++) { if(i == 0 || (i > 0 && nums[i] != nums[i-1])) { int l = i+1; int r = len-1; int target = 0 - nums[i]; while(l < r) { int tmp = nums[l] + nums[r]; if(target > tmp) { l++; } else if(target < tmp) { r--; } else{ res.push_back({nums[i],nums[l],nums[r]}); l++; r--; while(l < r && nums[l] == nums[l-1]) l++; while(l < r && nums[r] == nums[r+1]) r--; } } } } return res; } };给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数，使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。
例如，给定数组 nums = [-1，2，1，-4], 和 target = 1. 与 target 最接近的三个数的和为 2. (-1 + 2 + 1 = 2).思路和三数之和类似：先排序数组，遍历数组取第一个数(只到数组倒数第三个元素)，剩下两个数在第一个数的右边部分，定义双指针l和r分别指向i+1和len-1，当前三数和tmp = nums[l] + nums[r] + nums[i]，然后向中间移动，移动规则如下：
如果tmp < target，则++l，同时比较abs(tmp - target)和abs(res - target)，取较小值对应的那个三数和给结果res如果tmp > target，则–r，同时比较abs(tmp - target)和abs(res - target)，取较小值对应的那个三数和给结果res如果tmp == target，则tmp即为所求 时间复杂度：O(n2)空间复杂度：O(1)C++代码
class Solution { public: int threeSumClosest(vector<int>& nums, int target) { sort(nums.begin(),nums.end()); int len = nums.size(); if(len < 3) return INT_MAX; int res = nums[0] + nums[1] + nums[2]; for(int i=0;i<len-2;i++) { if(i == 0 || nums[i] != nums[i-1]) { int l = i+1,r = len-1; while(l < r) { int tmp = nums[l] + nums[r] + nums[i]; if(tmp < target) { res = abs(res - target) < abs(target - tmp) ? res : tmp; ++l; } else if(tmp > target) { res = abs(res - target) < abs(target - tmp) ? res : tmp; --r; } else{ return tmp; } if(i > 0) { while(l < r && nums[l] == nums[l-1]) ++l; while(l < r && nums[r] == nums[r+1]) --r; } } } } return res; } };双指针
class Solution { public: vector<vector<int>> fourSum(vector<int>& nums, int target) { vector<vector<int>>res; if(nums.size()<4) return res; sort(nums.begin(),nums.end()); for(int i=0;i<nums.size()-3;i++) { if(i>0 && nums[i]==nums[i-1])//去除重复 continue; for(int j=i+1;j<(int)nums.size()-2 ;j++) { if(j>i+1 && nums[j]==nums[j-1])//去除重复 continue; int left=j+1; int right=nums.size()-1; while(left<right) { int temp=nums[i]+nums[j]+nums[left]+nums[right]; if(temp==target) { res.push_back({nums[i],nums[j],nums[left],nums[right]}); while(left<right && nums[left]==nums[left+1])//去除重复 left++; while(left<right && nums[right]==nums[right-1])//去除重复 right--; left++; right--; } else if(temp<target) left++; else right--; } } } return res; } };26. 删除排序数组中的重复项
给定一个排序数组，你需要在 原地 删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。
不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。
示例 1:
给定数组 nums = [1,1,2], 函数应该返回新的长度 2, 并且原数组 nums 的前两个元素被修改为 1, 2。 你不需要考虑数组中超出新长度后面的元素。示例 2:
给定 nums = [0,0,1,1,1,2,2,3,3,4], 函数应该返回新的长度 5, 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4。 你不需要考虑数组中超出新长度后面的元素。 class Solution { public: int removeDuplicates(vector<int>& nums) { if(nums.empty()) return 0; int j=0; for(int i=1;i<nums.size();i++) { if(nums[i]!=nums[i-1]) j++; nums[j]=nums[i]; } return j+1; } };给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
示例:
输入: [0,1,0,3,12] 输出: [1,3,12,0,0]说明:
必须在原数组上操作，不能拷贝额外的数组。尽量减少操作次数。双指针法，快指针i遍历一遍数组，当快指针的元素非零时，令慢指针idx的元素等于快指针元素，同时慢指针前进一步。最后，所有的非零元素都移到了数组前半部分（相对顺序不变），然后将之后的元素全部置0。
时间复杂度：O(n)空间复杂度：O(1)C++代码
class Solution { public: void moveZeroes(vector<int>& nums) { if(nums.empty()) return; int idx = 0; for(int i=0;i<nums.size();i++) { if(nums[i] != 0) { nums[idx++] = nums[i]; } } for(;idx<nums.size();idx++) nums[idx] = 0; return; } };给定字符串 s 和 t ，判断 s 是否为 t 的子序列。
你可以认为 s 和 t 中仅包含英文小写字母。字符串 t 可能会很长（长度 ~= 500,000），而 s 是个短字符串（长度 <=100）。
字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，"ace“是”abcde“的一个子序列，而”aec"不是）。
示例 1:
s = “abc”, t = “ahbgdc”
返回 true.
示例 2:
s = “axc”, t = “ahbgdc”
返回 false.
后续挑战 :
如果有大量输入的 S，称作S1, S2, … , Sk 其中 k >= 10亿，你需要依次检查它们是否为 T 的子序列。在这种情况下，你会怎样改变代码？
双指针法，设置指针i和j分别指向字符串s和t
如果s[i] == t[j]，则i前进一步，j前进一步否则，j前进一步最后，判断指针i是否走完s，就能判断s是否为t的子序列。
时间复杂度：O(m+n)空间复杂度：O(1)C++代码
class Solution { public: bool isSubsequence(string s, string t) { int len = s.size(); int len1 = t.size(); if(len > len1) return false; int i = 0,j = 0; while(i < len && j < len1) { if(s[i] == t[j]) { i++; } j++; } if(i == len) return true; return false; } };给定 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。
示例:
输入: [1,8,6,2,5,4,8,3,7] 输出: 49双指针法，定义两个指针l和r分别指向数组两端，两个指针向中间移动，移动规则如下：
如果height[l] < height[r]，则++l否则，–r每走一步，计算容器装水量为左右边缘较小的那个高度乘边缘的的距离min(height[l],height[r]) * (r - l),然后和结果比较去较大值。
时间复杂度：O(n)空间复杂度：O(1)C++代码
class Solution { public: int maxArea(vector<int>& height) { int len = height.size(); if(len == 0) return 0; int res = 0; int l = 0; int r = len - 1; while(l < r) { int tmp = min(height[l],height[r]); int sum = (r - l)*tmp; if(height[l] < height[r]) ++l; else --r; res = max(res,sum); while(l < r && tmp == height[l]) ++l; while(l < r && tmp == height[r]) --r; } return res; } };合并两个有序数组
给定两个有序整数数组 nums1 和 nums2，将 nums2 合并到 nums1 中，使得 num1 成为一个有序数组。
说明:
初始化 nums1 和 nums2 的元素数量分别为 m 和 n。你可以假设 nums1 有足够的空间（空间大小大于或等于 m + n）来保存 nums2 中的元素。示例:
输入: nums1 = [1,2,3,0,0,0], m = 3 nums2 = [2,5,6], n = 3 输出: [1,2,2,3,5,6]双指针法，思路同合并两个有序链表
时间复杂度：O(m + n)空间复杂度：O(m + n)C++代码
class Solution { public: void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) { for(int i=m,j=0;i<m+n ;i++) nums1[i] = nums2[j++]; vector<int> vec(m + n,0); int l = 0; int r = m; int cnt = 0; while(l < m && r < m + n) { vec[cnt++] = nums1[l] < nums1[r] ? nums1[l++] : nums1[r++]; } while(l < m) vec[cnt++] = nums1[l++]; while(r < m + n) vec[cnt++] = nums1[r++]; copy(vec.begin(),vec.end(),nums1.begin()); } };54. 螺旋矩阵 给定一个包含 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]
class Solution { public: vector<int> spiralOrder(vector<vector<int>>& matrix) { vector<int>res; if(matrix.empty()) return res; int top=0,bottom=matrix.size()-1,left=0,right=matrix[0].size()-1; while(top<=bottom && left<=right) { for(int i=left;i<=right;i++) { res.push_back(matrix[top][i]); } for(int i=top+1;i<=bottom;i++) res.push_back(matrix[i][right]); for(int i=right-1;i>=left && bottom>top;i--) res.push_back(matrix[bottom][i]); for(int i=bottom-1;i>top && right>left;i--) res.push_back(matrix[i][left]); top++; bottom--; left++; right--; } return res; } };LeetCode中文
LeetCode英文
给定一个正整数 n，生成一个包含 1 到 n2 所有元素，且元素按顺时针顺序螺旋排列的正方形矩阵。
示例:
输入: 3 输出: [ [ 1, 2, 3 ], [ 8, 9, 4 ], [ 7, 6, 5 ] ]思路和 螺旋矩阵 相同，还是分层处理，不过螺旋矩阵是从矩阵读取值，这一题是写入值到矩阵。可以定义一个变量cnt用于全局计数，直到cnt等于n2的时候终止写入。
时间复杂度：O(n2)空间复杂度：O(n2)C++代码
class Solution { public: vector<vector<int>> generateMatrix(int n) { vector<vector<int>>res(n,vector<int>(n)); int top=0,bottom=n-1,left=0,right=n-1; int j=1; while(top<=bottom && left<=right) { for(int i=left;i<=right;i++) { res[top][i]=j; j++; } for(int i=top+1;i<=bottom;i++) { res[i][right]=j; j++; } for(int i=right-1;i>=top && top<bottom;i--) { res[bottom][i]=j; j++; } for(int i=bottom-1;i>top && left<right;i--) { res[i][left]=j; j++; } top++; bottom--; left++; right--; } return res; } };48. 旋转图像 给定一个 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] ]
class Solution { public: void rotate(vector<vector<int>>& matrix) { int n=matrix.size(); // transpose matrix for (int i = 0; i < n; i++) { for (int j = i; j < n; j++) { int tmp = matrix[j][i]; matrix[j][i] = matrix[i][j]; matrix[i][j] = tmp; } } // reverse each row for (int i = 0; i < n; i++) { for (int j = 0; j < n / 2; j++) { int tmp = matrix[i][j]; matrix[i][j] = matrix[i][n - j - 1]; matrix[i][n - j - 1] = tmp; } } } };73. 矩阵置零 给定一个 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] ] 进阶:
一个直接的解决方案是使用 O(mn) 的额外空间，但这并不是一个好的解决方案。 一个简单的改进方案是使用 O(m + n) 的额外空间，但这仍然不是最好的解决方案。 你能想出一个常数空间的解决方案吗？
class Solution { public: void setZeroes(vector<vector<int>>& matrix) { if(matrix.empty()) return; int m=matrix.size(); int n=matrix[0].size(); set<int>row,cols; for(int i=0;i<m;i++) { for(int j=0;j<n;j++) { if(matrix[i][j]==0) { row.insert(i); cols.insert(j); } } } // for(int i=0;i<m;i++) // { // for(int j=0;j<n;j++) // { // if(row.find(i)!=row.end() || cols.find(j)!=cols.end()) // matrix[i][j]=0; // } // } set<int>::iterator it; for(int i=0;i<m;i++) { for(it=cols.begin();it!=cols.end();it++) matrix[i][*it]=0; } for(int i=0;i<n;i++) { for(it=row.begin();it!=row.end();it++) matrix[*it][i]=0; } } };238.除自身以外数组的乘积
给定长度为 n 的整数数组 nums，其中 n > 1，返回输出数组 output ，其中 output[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积。
示例:
输入: [1,2,3,4] 输出: [24,12,8,6]说明: 请不要使用除法，且在 O(n) 时间复杂度内完成此题。
进阶：
你可以在常数空间复杂度内完成这个题目吗？（ 出于对空间复杂度分析的目的，输出数组不被视为额外空间。）
方法1
由于output[i] = nums[0]*nums[1]*...*nums[i-1]*nums[i+1]*...*nums[len-1],可以将output[i]分为两部分，前半部分为C[i] = nums[0]*nums[1]*...*nums[i-1],后半部分为D[i] = nums[i+1]*...*nums[len-1]。可以发现规律，数组C和D相邻元素之间存在递推关系：
C[i] = C[i-1]*nums[i-1] (i = 1~len-1) D[i] = D[i+1]*nums[i+1] (i = 0~len-2)因此求出数组output的每一项output[i] = C[i]*D[i]。
时间复杂度：O(n)空间复杂度：O(n)C++代码
class Solution { public: vector<int> productExceptSelf(vector<int>& nums) { int len = nums.size(); if(len == 0) return nums; vector<int> res(len,1); vector<int> C(len,1); vector<int> D(len,1); for(int i=1;i<len;i++) { C[i] = nums[i-1]*C[i-1]; } for(int i=len-2;i>=0;i--) { D[i] = D[i+1]*nums[i+1]; } for(int i=0;i<len;i++) { res[i] = C[i]*D[i]; } return res; } };方法2：优化空间复杂度
先将数组C的数值计算到输出数组res中，然后定义一个变量tmp代替数组D的递推关系计算，对数组res从后向前进行递推计算得出最终结果。可以优化空间复杂度到常数时间。
时间复杂度：O(n) (输出数组不被视为额外空间)空间复杂度：O(1)C++代码
class Solution { public: vector<int> productExceptSelf(vector<int>& nums) { int len = nums.size(); if(len == 0) return nums; vector<int> res(len,1); for(int i=1;i<len;i++) { res[i] = res[i-1] * nums[i-1]; } int tmp = 1; for(int i=len-2;i>=0;i--) { tmp *= nums[i+1]; res[i] *= tmp; } return res; } };74. 搜索二维矩阵
编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性：
每行中的整数从左到右按升序排列。 每行的第一个整数大于前一行的最后一个整数。 示例 1:
输入: matrix = [ [1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 50] ] target = 3 输出: true
示例 2:
输入: matrix = [ [1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 50] ] target = 13 输出: false
class Solution { public: bool searchMatrix(vector<vector<int>>& matrix, int target) { int m=matrix.size(); if(m==0) return false; int n=matrix[0].size(); int left=0,right=m*n-1; int mid,mid_matrix; while(left<=right) { mid=(left+right)/2; mid_matrix=matrix[mid/n][mid%n]; if(target==mid_matrix) return true; else if(target<mid_matrix) right=mid-1; else left=mid+1; } return false; } }; if(matrix.empty()) return false; int row=0; int column=matrix[0].size()-1; while(row<matrix.size()&& column>=0) { if(target==matrix[row][column]) return true; else if(target<matrix[row][column]) column--; else row++; } return false;给定一个非负整数 numRows，生成杨辉三角的前 numRows 行。
在杨辉三角中，每个数是它左上方和右上方的数的和。
示例:
输入: 5 输出: [ [1], [1,1], [1,2,1], [1,3,3,1], [1,4,6,4,1] ] 解答利用杨辉三角的性质，利用上一行的数值推导出下一行，推导关系式为：
时间复杂度：O(n2)空间复杂度：O(n2)C++代码
class Solution { public: vector<int> transform(vector<int> vec) { vector<int> res; res.push_back(1); int len = vec.size(); for(int i=1;i<len;i++) { res.push_back(vec[i-1] + vec[i]); } res.push_back(1); return res; } vector<vector<int>> generate(int numRows) { vector<vector<int>> res; if(numRows == 0) return res; if(numRows == 1) { res.push_back({1}); return res; } res.push_back({1}); for(int i=1;i<numRows;i++) { res.push_back(transform(res[i-1])); } return res; } };Python代码
给定一个包含 0, 1, 2, ..., n 中 n 个数的序列，找出 0 .. n 中没有出现在序列中的那个数。
示例 1:
输入: [3,0,1] 输出: 2示例 2:
输入: [9,6,4,2,3,5,7,0,1] 输出: 8说明:
你的算法应具有线性时间复杂度。你能否仅使用额外常数空间来实现?
方法1：位运算
将原数组的所有元素和0~n的所有数字做异或运算，得到结果就是缺失的数字
时间复杂度：O(n)空间复杂度：O(1)C++代码
class Solution { public: int missingNumber(vector<int>& nums) { int res = 0; for(int i=0;i<nums.size();i++) { res ^= (i + 1) ^ nums[i]; } return res; } };方法2：等差数列
等差数列求0~n的和减去数组所有元素相加得到的和即为缺失的数字
时间复杂度：O(n)空间复杂度：O(1)C++代码
class Solution { public: int missingNumber(vector<int>& nums) { int sum = 0; int n = nums.size(); for(auto num : nums) sum += num; return (int)((1 + n) * n / 2) - sum; } };189.旋转数组
给定一个数组，将数组中的元素向右移动 k 个位置，其中 k 是非负数。
示例 1:
输入: [1,2,3,4,5,6,7] 和 k = 3 输出: [5,6,7,1,2,3,4] 解释: 向右旋转 1 步: [7,1,2,3,4,5,6] 向右旋转 2 步: [6,7,1,2,3,4,5] 向右旋转 3 步: [5,6,7,1,2,3,4]示例 2:
输入: [-1,-100,3,99] 和 k = 2 输出: [3,99,-1,-100] 解释: 向右旋转 1 步: [99,-1,-100,3] 向右旋转 2 步: [3,99,-1,-100]说明:
尽可能想出更多的解决方案，至少有三种不同的方法可以解决这个问题。要求使用空间复杂度为 O(1) 的原地算法。 方法1设数组的长度为len，k对len取模得到k1 = k % len，开辟一个新数组cp拷贝nums，nums的值清空，然后进行如下步骤：
将cp数组的最后k1个元素添加到数组nums尾部将cp数组的开始len-k1个元素添加到数组nums尾部 时间复杂度：O(n)空间复杂度：O(n)C++代码
class Solution { public: void rotate(vector<int>& nums, int k) { int len = nums.size(); int k1 = k%len; vector<int> cp(nums); nums.clear(); copy(cp.end() - k1,cp.end(),back_inserter(nums)); copy(cp.begin(),cp.end() - k1,back_inserter(nums)); } }; 方法2设数组的长度为len，k对len取模得到k1 = k % len，然后进行如下步骤：
反转数组的最后k1个元素反转数组的前面len - k1个元素反转整个数组最后得到的数组的就是旋转之后的数组
时间复杂度：O(n)空间复杂度：O(1)C++代码
class Solution { public: void rotate(vector<int>& nums, int k) { if(k == nums.size()) return; int len = nums.size(); int k1 = k % len; reverse(nums.begin(),nums.end() - k1); reverse(nums.end() - k1,nums.end()); reverse(nums.begin(),nums.end()); } };278.寻找重复数
给定一个包含 n + 1 个整数的数组 nums，其数字都在 1 到 n 之间（包括 1 和 n），可知至少存在一个重复的整数。假设只有一个重复的整数，找出这个重复的数。
示例 1:
输入: [1,3,4,2,2] 输出: 2示例 2:
输入: [3,1,3,4,2] 输出: 3说明：
不能更改原数组（假设数组是只读的）。只能使用额外的 O(1) 的空间。时间复杂度小于 O(n2) 。数组中只有一个重复的数字，但它可能不止重复出现一次。遍历数组，判断当前元素nums[i]是否和位置i+1相等：
如果nums[i] == i+1，则nums[i]位于它自己的位置，++i遍历下一个元素；否则，找到位置是nums[i]-1位置的元素nums[nums[i] - 1]： 如果nums[nums[i] - 1] == nums[i],则找到重复元素nums[i]否则，交换nums[nums[i] - 1]和nums[i] 重复情况2的过程，直到nums[i] == i+1时，执行情况1。 时间复杂度：O(n)空间复杂度：O(1)C++代码
class Solution { public: int findDuplicate(vector<int>& nums) { if(nums.empty()) return 0; for(int i=0;i<nums.size();i++) { while(nums[i] != i+1) { int tmp = nums[i]; if(nums[tmp-1] == tmp) return tmp; swap(nums[i],nums[tmp-1]); } } return -1; } };56. 合并区间
给出一个区间的集合，请合并所有重叠的区间。
示例 1:
输入: [[1,3],[2,6],[8,10],[15,18]] 输出: [[1,6],[8,10],[15,18]] 解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
示例 2:
输入: [[1,4],[4,5]] 输出: [[1,5]] 解释: 区间 [1,4] 和 [4,5] 可被视为重叠区间。
class Solution { public: vector<vector<int>> merge(vector<vector<int>>& intervals) { vector<vector<int>>res; if(intervals.size()==0 || intervals.size()==1) return intervals; sort(intervals.begin(),intervals.end(),[&,this](vector<int>&v1,vector<int>&v2) {return v1[0]<v2[0];}); for(int i=0;i<intervals.size();i++) { vector<int>temp=intervals[i]; while(i+1<intervals.size() && temp[1]>=intervals[i+1][0])//循环 { ++i; temp[1]=max(temp[1],intervals[i][1]); } res.push_back(temp); } return res; } };LeetCode中文
实现获取下一个排列的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。
如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。
必须原地修改，只允许使用额外常数空间。
以下是一些例子，输入位于左侧列，其相应输出位于右侧列。
1,2,3 → 1,3,2 3,2,1 → 1,2,3 1,1,5 → 1,5,1
此题需要找出规律，举一个例子来说明，有如下的一个数组
1 2 7 4 3 1下一个排列为：
1 3 1 2 4 7那么是如何得到的呢，我们通过观察原数组可以发现，如果从末尾往前看，数字逐渐变大，到了2时才减小的，然后我们再以这个2的位置的后一个位置开始，从前往后找第一个比2大的数字，是3，那么我们交换2和3，再把此时3后面的所有数字（不包括3的位置）反转一下即可，步骤如下：
1 2 7 4 3 1 1 2 7 4 3 1 1 3 7 4 2 1 1 3 1 2 4 7再举几个例子验证仍然符合这个规律。因此，处理过程可总结以下几个步骤：
从后往前遍历数组，找到数值开始减小的那个位置idx，即nums[idx-1] < nums[idx]；令idx_l = idx-1，从idx位置从前往后移动直到找到最后一个数值大于nums[idx_l]的元素；交换nums[idx_l]和nums[idx]的值；反转数组在idx位置之后的所有元素。最后，就可以得到下一个排列。
时间复杂度：O(n)空间复杂度：O(1)C++代码
class Solution { public: void nextPermutation(vector<int>& nums) { int len = nums.size(); if(len <= 0) return; int idx = len - 1; for(;idx >= 1 && nums[idx-1] >= nums[idx];idx--); if(idx == 0) { reverse(nums.begin(),nums.end()); return; } int idx_l = idx - 1; for(int i=idx;idx<len;idx++) { if(nums[idx] <= nums[idx_l]) break; } swap(nums[idx-1],nums[idx_l]); reverse(nums.begin() + idx_l + 1,nums.end()); return; } };41.缺失的第一个正数
给定一个未排序的整数数组，找出其中没有出现的最小的正整数。
示例 1:
输入: [1,2,0] 输出: 3示例 2:
输入: [3,4,-1,1] 输出: 2示例 3:
输入: [7,8,9,11,12] 输出: 1说明:
你的算法的时间复杂度应为O(n)，并且只能使用常数级别的空间。
方法1使用unordered_set结构的集合st装入nums中的元素，同时找到nums元素的最大值Max，然后遍历1~Max范围内的数，找到第一个不在集合st中数就是缺失的第一个正数，如果都在集合st中，那么缺失的第一个正数就在1和Max+1的较小值中取得。
时间复杂度：O(n)空间复杂度：O(n)C++代码
class Solution { public: int firstMissingPositive(vector<int>& nums) { unordered_set<int> st; int Max = INT_MIN; for(auto a : nums) { st.insert(a); Max = max(Max,a); } for(int i=1;i<=Max;i++) { if(st.count(i) == 0) return i; } return max(Max + 1,1); } }; 方法2：优化空间复杂度对于大小为n（n>0）的数组，这n个数可以分为以下几种情况：
这n个数都小于等于0这n个数都大于n存在一个或多个位于[1,n]的数对于情况1和情况2，要查找的第一个缺失的正数就是1；
问题是对于情况3应该怎么考虑呢？
假设这些位于[1,n]的数i，在数组中的位置应该为i-1，而小于等于0的数，以及大于n的数，在数组剩余位置：
如果数组所有的数都在[1,n]，那么每个元素都在其值减1的位置，此时要找的第一个缺失的整数就是n+1；否则，数组中，必然存在一个位置idx，其元素值不等于idx+1，而范围[1,n]就是正数序列最开始的n个数，因此，从左往右查找第一个下标加1不等于值的位置，那么要找的第一个缺失的正数就是该位置的下标加1。注意：交换元素的方法可以将范围在[1,n]的元素放置到正确的位置,详见 寻找重复数
时间复杂度：O(n)空间复杂度：O(1)C++代码
class Solution { public: int firstMissingPositive(vector<int>& nums) { int len = nums.size(); if(len == 0) return 1; for(int i=0;i<len;i++) { while(nums[i] > 0 && nums[i] <= len && nums[i] != i+1 && nums[nums[i] - 1] != nums[i]) { swap(nums[nums[i] - 1],nums[i]); } } for(int i=0;i<len;i++) { if(nums[i] != i + 1) return i + 1; } return len + 1; } };