给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？找出所有满足条件且不重复的三元组。
注意：答案中不可以包含重复的三元组。
示例 给定数组 nums = [-1, 0, 1, 2, -1, -4]， 满足要求的三元组集合为： [ [-1, 0, 1], [-1, -1, 2] ]
C++ 参考代码
class Solution { public: vector<vector<int>> threeSum(vector<int>& nums) { int n = nums.size(); sort(nums.begin(),nums.end()); if(n < 3) return {}; vector<vector<int>>ans; for(int i = 0;i<n;++i){ if(nums[i]>0)return ans; if(i > 0 && nums[i] == nums[i-1]){ continue; } int left = i+1; int right = n-1; while(left < right){ if(nums[i] + nums[left]+nums[right]==0){ ans.push_back({nums[i],nums[left],nums[right]}); while(left < right && nums[left] == nums[left+1]){ left+=1; } while(left < right && nums[right]== nums[right-1]){ right-=1; } left+=1; right-=1; } else if(nums[i]+nums[left]+nums[right]>0){ right-=1; }else{ left+=1; } } } return ans; } };给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数，使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。
示例 例如，给定数组 nums = [-1，2，1，-4], 和 target = 1. 与 target 最接近的三个数的和为 2. (-1 + 2 + 1 = 2).
思路：先排序，然后利用双指针，如果直接遍历，时间复杂度很高
class Solution { public: int threeSumClosest(vector<int>& nums, int target) { sort(nums.begin(),nums.end()); int ans = INT_MAX,ant = 0; for(int i = 0;i<nums.size()-2;++i){ int j = i+1; int k = nums.size()-1; while(j<k){ int sum = nums[i]+nums[j]+nums[k]; if(sum == target){ return target; } else if(sum < target){ if(abs(sum-target) < ans){ ans = abs(sum-target); ant = sum; } j+=1; }else{ if(abs(sum-target) < ans){ ans = abs(sum-target); ant = sum; } k-=1; } } } return ant; } };实现获取下一个排列的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。
如果不存在下一个更大的排列，则将数字重新排列成最小的排列
示例 1,2,3 → 1,3,2 3,2,1 → 1,2,3 1,1,5 → 1,5,1
假设 我们的数1376542 ,我们第一要找的位置就是 3 ，把 3 和 4 进行交换，然后对3后面的数字进行翻转。
可以看出，需要改变的子数组的起始数为 从后往前第一个nums[i]>nums[i-1]的数 k，即3；要把起始数k替换为从后往前第一个大于k的数，即4，交换两数变为1476532 翻转 i 之后的一半数组
有一种特殊情况：倒序遍历到0都没有碰到 nums[i]>nums[i-1] 的情况，直接翻转整个数组 最后结果就是：1423567
class Solution { public: void nextPermutation(vector<int>& nums) { int n = nums.size(); int i = n-1, j = n-1; while(i>0 && nums[i-1]>=nums[i]){ i-=1; } int k = i-1; if(k>=0){ while(nums[j]<=nums[k]){ j-=1; } swap(nums[k],nums[j]); } int left = k+1,right = n-1; while(left < right){ swap(nums[left],nums[right]); left+=1; right-=1; } } };给定一个未排序的整数数组，找出其中没有出现的最小的正整数
示例1 输入: [1,2,0] 输入: [7,8,9,11,12] 输出: 3 输出: 1
思路：对位置进行判断，如果当前元素不在对应的正确位置，比如 1 不在第一个位置，则把它和 ‘当前位置下标-1’ 的元素进行交换，最后遍历最小正整数
class Solution { public: // 时间复杂度为O(N),空间为O(1) int firstMissingPositive(vector<int>& nums) { // 进行调整 for(int i = 0;i<nums.size();++i){ adjust(nums,i); } for(int i = 0;i<nums.size();++i){ if(nums[i]-1 != i){ return i +1; } } return nums.size()+1; } void adjust(vector<int>&nums,int i){ while(nums[i] > 0 && nums[i]<=nums.size() \ && nums[nums[i] - 1] != nums[i] ){ swap(nums[nums[i] - 1], nums[i]); } } };给定一个未排序的数组，判断这个数组中是否存在长度为 3 的递增子序列
如果存在这样的 i, j, k, 且满足 0 ≤ i < j < k ≤ n-1， 使得 arr[i] < arr[j] < arr[k] ，返回 true ; 否则返回 false 。 说明: 要求算法的时间复杂度为 O(n)，空间复杂度为 O(1)
示例1 输入: [1,2,3,4,5] 输出: true
示例2 输入: [5,4,3,2,1] 输出: false
思路：由于要找出三个递增序列，所以只要定义两个变量，遍历数组，当前的最小值可以做 first，如果当前元素大于 first 则赋值给 second，然后只要遍历到一个元素大于 second 就可以返回True，否则返回 False
bool increasingTriplet(vector<int>& nums) { int first = INT_MAX; int second = INT_MAX; for(int i = 0;i<nums.size();++i){ // 请注意这里的符号 // 由于是递增，所以不允许值相等的情况，也就是说不允许 // first 和 second 相等 if(first>=nums[i]){ first = nums[i]; }else if(second > nums[i]){ second = nums[i]; }else if(nums[i]>second){ return true; } } return false; }在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。 即输出P%1000000007
输入描述:题目保证输入的数组中没有的相同的数字
示例1 输入 1,2,3,4,5,6,7,0 输出 7
递归排序的思想
int InversePairs(vector<int> data) { int size = data.size(); if(size == 0){ return 0; } vector<int>copy(data); long long count = InversePairs(data,copy,0,size-1); return count%1000000007; } long long InversePairs(vector<int>&data,vector<int>©,\ int start,int end){ if(start == end){ copy[start] = data[start]; return 0; } int length = (end-start)/2; long long left = InversePairs(copy,data,start,start+length); long long right = InversePairs(copy,data,start+length+1,end); // 初始化前半段最后一个下标和后半段 int i = start + length; int j = end; int index = end; long long count = 0; while(i>=start && j>=start+length+1){ if(data[i]>data[j]){ copy[index--] = data[i--]; count += j-start-length; }else{ copy[index--] = data[j--]; } } for(;i>=start;--i){ copy[index--] = data[i]; } for(;j>=start+length+1;--j){ copy[index--] = data[j]; } return left+right+count; }给定一个无序数组arr, 其中元素可正、可负、可0。给定一个整数k，求arr所有子数组中累加和为k的最长子数组长度
示例1 输入 5 0 1 -2 1 1 1 输出3
int func(vector<int>&v,int k){ int n = v.size(); int ans = 0,s = 0; map<int,int>mp; mp[0] = -1; for(int i = 0;i<n;++i){ s += v[i]; if(mp.find(s-k) != mp.end()){ ans = max(ans,i-mp[s-k]); } if(mp.find(s) == mp.end()){ mp[s] = i; } } return ans; }给出一个区间的集合，请合并所有重叠的区间。
示例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) { if (intervals.size() == 0) { return {}; } sort(intervals.begin(), intervals.end()); vector<vector<int>> merged; for (int i = 0; i < intervals.size(); ++i) { int L = intervals[i][0], R = intervals[i][1]; if (!merged.size() || merged.back()[1] < L) { merged.push_back({L, R}); } else { merged.back()[1] = max(merged.back()[1], R); } } return merged; } };给定一个正整数 n，生成一个包含 1 到 n2 所有元素，且元素按顺时针顺序螺旋排列的正方形矩阵
示例 输入: 3 输出: [ [ 1, 2, 3 ], [ 8, 9, 4 ], [ 7, 6, 5 ] ]
class Solution { public: vector<vector<int>> generateMatrix(int n) { vector<vector<int>>v(n,vector<int>(n)); vector<vector<bool>>book(n,vector<bool>(n)); int dx[4] = {-1,0,1,0},dy[4] = {0,1,0,-1}; int x = 0,y = 0,d = 1; for(int i = 1;i<n*n+1;++i){ v[x][y] = i; book[x][y] = true; int a = x + dx[d]; int b = y + dy[d]; if(a < 0 || a>=n || b< 0 || b>=n || book[a][b]){ d = (d+1)%4; a = x+dx[d],b = y+dy[d]; } x = a,y = b; } return v; } };在上一题的基础上，额外加一个条件，就是机器人在行走的时候可能会遇到障碍，遇到阻碍后就无法向它本来的方向行走了，只能改变方向。
示例 输入: [ [0,0,0], [0,1,0], [0,0,0] ] 输出: 2
定义一个二维数组，如果遇到 1，则置位0，其他的是按照左边和上边的值和计算
也可以定义一个一维数组，只保存一行就可以了，每一行都是在上一行的基础上进行计算的
参考代码！
class Solution { public: int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) { int row = obstacleGrid.size(); int col = obstacleGrid[0].size(); vector<int>dp(col); dp[0] = (obstacleGrid[0][0]==0); for (int i = 0; i < row; ++i) { for (int j = 0; j < col; ++j) { if (obstacleGrid[i][j] == 1) { dp[i] = 0; continue; } if(j >0 && obstacleGrid[i][j-1] == 0){ dp[j] += dp[j-1]; } } } return dp.back(); } };