问题
给定一个包含 0, 1, 2, …, n 中 n 个数的序列，找出 0 … n 中没有出现在序列中的那个数。
示例 1:
输入: [3,0,1] 输出: 2 示例 2:
输入: [9,6,4,2,3,5,7,0,1] 输出: 8
说明: 你的算法应具有线性时间复杂度。你能否仅使用额外常数空间来实现?
题解
不符合说明的方法
新建一个n+1大小的数组，作为flag，遍历nums，将出现的数字在flag数组对应的位置标注为1.
最后遍历flag，出现0 的位置即为缺少数字
class Solution { public: int missingNumber(vector<int>& nums) { int *s = new int[nums.size()+1]; for(auto i : nums) s[i]=1; for(int i =0;i<nums.size()+1;i++){ if(s[i] != 1) return i; } return 0; } }; 时间复杂度O(N)空间复杂度O(N)哈希表
总是忘了用哈希表，难受！！
class Solution: def missingNumber(self, nums): num_set = set(nums) n = len(nums) + 1 for number in range(n): if number not in num_set: return number 时间复杂度：O(n)。集合的插入操作的时间复杂度都是 O(1)，一共插入了 n 个数，时间复杂度为 O(n)。集合的查询操作的时间复杂度同样是 O(1)，最多查询 n+1 次，时间复杂度为 O(n)。因此总的时间复杂度为 O(n)。空间复杂度：O(n)。集合中会存储 n 个数，因此空间复杂度为 O(n)。位运算
强！！！！！！！
由于异或运算（XOR）满足结合律，并且对一个数进行两次完全相同的异或运算会得到原来的数，因此我们可以通过异或运算找到缺失的数字。
算法
我们知道数组中有 nn 个数，并且缺失的数在 [0…n][0…n] 中。因此我们可以先得到 [0…n][0…n] 的异或值，再将结果对数组中的每一个数进行一次异或运算。未缺失的数在 [0…n][0…n] 和数组中各出现一次，因此异或后得到 0。而缺失的数字只在 [0…n][0…n] 中出现了一次，在数组中没有出现，因此最终的异或结果即为这个缺失的数字。
class Solution: def missingNumber(self, nums): missing = len(nums) for i, num in enumerate(nums): missing ^= i ^ num return missing 时间复杂度O(N)空间复杂度O(1)数学
高斯求和公式求出前n个数的和，减去数组中所有数的和，就得到了缺失的数字
实际上有风险，数据容易溢出
class Solution: def missingNumber(self, nums): expected_sum = len(nums)*(len(nums)+1)//2 actual_sum = sum(nums) return expected_sum - actual_sum 时间复杂度O(N) 求出数组中所有数的和的时间复杂度为 O(n)空间复杂度O(1)问题
给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
示例:
输入: [0,1,0,3,12] 输出: [1,3,12,0,0] 说明:
必须在原数组上操作，不能拷贝额外的数组。 尽量减少操作次数。
代码模板
class Solution { public: void moveZeroes(vector<int>& nums) { } };题解
很简单，想一想就知道法
我的应该就是最好的
记录0的个数，遍历数组，遇0加一，遇非零数移位到前面的首个0位置。
class Solution { public: void moveZeroes(vector<int>& nums) { int zero_num = 0; int s = nums.size(); for(int i=0;i<s;i++){ if(nums[i]==0) zero_num++; else{ if(zero_num != 0){ nums[i-zero_num]=nums[i]; nums[i] = 0; } } } } }; 时间复杂度O(N)空间复杂度O(1)官方最优解法
和我的异曲同工！！！
就是比我写的简介
当我们遇到一个非零元素时，我们需要交换当前指针和慢速指针指向的元素，然后前进两个指针。如果它是零元素，我们只前进当前指针。
void moveZeroes(vector<int>& nums) { for (int lastNonZeroFoundAt = 0, cur = 0; cur < nums.size(); cur++) { if (nums[cur] != 0) { swap(nums[lastNonZeroFoundAt++], nums[cur]); } } } 时间复杂度O(N)空间复杂度O(1)问题
给定一个非空数组，返回此数组中第三大的数。如果不存在，则返回数组中最大的数。要求算法时间复杂度必须是O(n)。
示例 1:
输入: [3, 2, 1]
输出: 1
解释: 第三大的数是 1. 示例 2:
输入: [1, 2]
输出: 2
解释: 第三大的数不存在, 所以返回最大的数 2 . 示例 3:
输入: [2, 2, 3, 1]
输出: 1
解释: 注意，要求返回第三大的数，是指第三大且唯一出现的数。 存在两个值为2的数，它们都排第二。
题解
class Solution { public: int thirdMax(vector<int>& nums) { int min = nums[0]; for(auto i:nums){ if(i<min) min = i; } int max1=min; int max2=min; int max3=min; for(auto i:nums){ if(i>max1){ max3 = max2; max2 = max1; max1 = i; } else if(i>max2 && i<max1){ max3 = max2; max2 = i; } else if(i>max3 && i<max2) max3 = i; } return max3==max2?max1:max3; } }; 时间复杂度O(N)空间复杂度O(1)问题
给定一个范围在 1 ≤ a[i] ≤ n ( n = 数组大小 ) 的 整型数组，数组中的元素一些出现了两次，另一些只出现一次。
找到所有在 [1, n] 范围之间没有出现在数组中的数字。
您能在不使用额外空间且时间复杂度为O(n)的情况下完成这个任务吗? 你可以假定返回的数组不算在额外空间内。
示例:
输入: [4,3,2,7,8,2,3,1]
输出: [5,6]
题解
看着别人的思路做出来的答案
class Solution { public: vector<int> findDisappearedNumbers(vector<int>& nums) { vector<int> disappear; for(int i=1;i<nums.size()+1;i++){ if(nums[i-1]>0 && nums[nums[i-1]-1]>0) nums[nums[i-1]-1]*=-1; else if(nums[i-1]<0 && nums[-nums[i-1]-1]>0) nums[-nums[i-1]-1]*=-1; } for(int i=1;i<nums.size()+1;i++){ if(nums[i-1]>0) disappear.push_back(i); } return disappear; } }; 时间复杂度O(N)空间复杂度O(1)和上一个解法一样，但更简洁
vector<int> findDisappearedNumbers(vector<int>& nums) { for (int i = 0; i < nums.size(); ++i) nums[abs(nums[i])-1] = -abs(nums[abs(nums[i])-1]); vector<int> res; for (int i = 0; i < nums.size(); ++i){ if (nums[i] > 0) res.push_back(i+1); } return res; } 时间复杂度O(N)空间复杂度O(1)给定一个二进制数组， 计算其中最大连续1的个数。
示例 1:
输入: [1,1,0,1,1,1] 输出: 3 解释: 开头的两位和最后的三位都是连续1，所以最大连续1的个数是 3. 注意：
输入的数组只包含 0 和1。 输入数组的长度是正整数，且不超过 10,000。
题解
没啥好说的，太简单那了
class Solution { public: int findMaxConsecutiveOnes(vector<int>& nums) { int max=0; int cur=0; for(int i=0;i<nums.size();i++){ if(nums[i]==1) cur++; else{ if(cur>max) max=cur; cur = 0; } } if(cur>max) max=cur; return max; } }; 时间复杂度O(N)空间复杂度O(1)python骚操作
在 Python 中可以使用 map 和 join 来解决此问题。 使用 splits 函数在 0 处分割将数组转换成字符串。 在获取子串的最大长度就是最大连续 1 的长度。
def findMaxConsecutiveOnes(self, nums): return max(map(len, ''.join(map(str, nums)).split('0')))问题
斐波那契数，通常用 F(n) 表示，形成的序列称为斐波那契数列。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：
F(0) = 0, F(1) = 1 F(N) = F(N - 1) + F(N - 2), 其中 N > 1. 给定 N，计算 F(N)。
示例 1：
输入：2 输出：1 解释：F(2) = F(1) + F(0) = 1 + 0 = 1. 示例 2：
输入：3 输出：2 解释：F(3) = F(2) + F(1) = 1 + 1 = 2.
题解
最简单之递归法
class Solution { public: int fib(int N) { if(N ==0) return 0; if(N ==1) return 1; return fib(N-1)+fib(N-2); } }; 时间复杂度O(2**N)空间复杂度O(N)记忆化自底向上的方法
class Solution: def fib(self, N: int) -> int: if N <= 1: return N return self.memoize(N) def memoize(self, N: int) -> {}: cache = {0: 0, 1: 1} # Since range is exclusive and we want to include N, we need to put N+1. for i in range(2, N+1): cache[i] = cache[i-1] + cache[i-2] return cache[N] 时间复杂度：O(N)O(N)。空间复杂度：O(N)O(N)，使用了空间大小为 N 的数组。记忆化自顶向下的方法
class Solution: def fib(self, N: int) -> int: if N <= 1: return N self.cache = {0: 0, 1: 1} return self.memoize(N) def memoize(self, N: int) -> {}: if N in self.cache.keys(): return self.cache[N] self.cache[N] = self.memoize(N-1) + self.memoize(N-2) return self.memoize(N) 时间复杂度：O(N)O(N)。空间复杂度：O(N)O(N)，内存中使用的堆栈大小。方法四：自底向上进行迭代
class Solution: def fib(self, N: int) -> int: if (N <= 1): return N if (N == 2): return 1 current = 0 prev1 = 1 prev2 = 1 # Since range is exclusive and we want to include N, we need to put N+1. for i in range(3, N+1): current = prev1 + prev2 prev2 = prev1 prev1 = current return current 时间复杂度：O(N)O(N)。空间复杂度：O(1)O(1)，仅仅使用了 current，prev1，prev2矩阵求幂法
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-FLLfr1AE-1603169242729)(1595642271261.png)]
class Solution: def fib(self, N: int) -> int: if (N <= 1): return N A = [[1, 1], [1, 0]] self.matrix_power(A, N-1) return A[0][0] def matrix_power(self, A: list, N: int): if (N <= 1): return A self.matrix_power(A, N//2) self.multiply(A, A) B = [[1, 1], [1, 0]] if (N%2 != 0): self.multiply(A, B) def multiply(self, A: list, B: list): x = A[0][0] * B[0][0] + A[0][1] * B[1][0] y = A[0][0] * B[0][1] + A[0][1] * B[1][1] z = A[1][0] * B[0][0] + A[1][1] * B[1][0] w = A[1][0] * B[0][1] + A[1][1] * B[1][1] A[0][0] = x A[0][1] = y A[1][0] = z A[1][1] = w 时间复杂度：O(\log N)O(logN)。空间复杂度：O(\log N)O(logN)，matrixPower 函数递归时堆栈使用的空间。公式法
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-F8xAVkBt-1603169242730)(1595642384349.png)]
# Contributed by LeetCode user mereck. class Solution: def fib(self, N): golden_ratio = (1 + 5 ** 0.5) / 2 return int((golden_ratio ** N + 1) / 5 ** 0.5)时间复杂度：O(1)O(1)。常数的时间复杂度，因为我们是基于 Binet 公式进行计算，没有使用循环或递归。 空间复杂度：O(1)O(1)，存储黄金分割率所使用的空间。
问题
给定长度为 2n 的数组, 你的任务是将这些数分成 n 对, 例如 (a1, b1), (a2, b2), …, (an, bn) ，使得从1 到 n 的 min(ai, bi) 总和最大。
示例 1:
输入: [1,4,3,2]
输出: 4 解释: n 等于 2, 最大总和为 4 = min(1, 2) + min(3, 4). 提示:
n 是正整数,范围在 [1, 10000]. 数组中的元素范围在 [-10000, 10000].
代码模板
class Solution { public: int arrayPairSum(vector<int>& nums) { } };题解
排序，遍历数组，步幅为2；依次将2个相邻的数字作为一对。
class Solution { public: int arrayPairSum(vector<int>& nums) { sort(nums.begin(),nums.end()); int ans=0; for(int i=0;i<nums.size();i+=2) ans += nums[i]; return ans; } }; 时间复杂度O(NlogN)空间复杂度O(1)python美学
class Solution(object): def arrayPairSum(self, nums): """ :type nums: List[int] :rtype: int """ #[::2]从0到最后一位隔2个取一个 return sum(sorted(nums)[::2])问题
给定一个非空且只包含非负数的整数数组 nums, 数组的度的定义是指数组里任一元素出现频数的最大值。
你的任务是找到与 nums 拥有相同大小的度的最短连续子数组，返回其长度。
示例 1:
输入: [1, 2, 2, 3, 1] 输出: 2 解释: 输入数组的度是2，因为元素1和2的出现频数最大，均为2. 连续子数组里面拥有相同度的有如下所示: [1, 2, 2, 3, 1], [1, 2, 2, 3], [2, 2, 3, 1], [1, 2, 2], [2, 2, 3], [2, 2] 最短连续子数组[2, 2]的长度为2，所以返回2. 示例 2:
输入: [1,2,2,3,1,4,2] 输出: 6 注意:
nums.length 在1到50,000区间范围内。 nums[i] 是一个在0到49,999范围内的整数。
题解
问题
给你个整数数组 arr，其中每个元素都 不相同。
请你找到所有具有最小绝对差的元素对，并且按升序的顺序返回。
示例 1：
输入：arr = [4,2,1,3] 输出：[[1,2],[2,3],[3,4]] 示例 2：
输入：arr = [1,3,6,10,15] 输出：[[1,3]] 示例 3：
输入：arr = [3,8,-10,23,19,-4,-14,27] 输出：[[-14,-10],[19,23],[23,27]]
提示：
2 <= arr.length <= 10^5 -10^6 <= arr[i] <= 10^6
题解
排序遍历
先排序，遍历一次寻找最小值，再遍历一次找出所有最小值的数字对。
class Solution { public: vector<vector<int>> minimumAbsDifference(vector<int>& arr) { vector<vector<int>> ans; sort(arr.begin(),arr.end()); int min=abs(arr[0]-arr[1]); for(int i=0;i<arr.size()-1;i++){ if(abs(arr[i]-arr[i+1])<min) min = abs(arr[i]-arr[i+1]); } for(int i=0;i<arr.size()-1;i++){ if(abs(arr[i]-arr[i+1])==min) ans.push_back(vector<int>{arr[i],arr[i+1]}); } return ans; } }; 时间复杂度O(N*log(N))空间复杂度O(1) 不包括返回ans占用的空间。问题
给你一个整数数组 nums，请你返回其中位数为 偶数 的数字的个数。
示例 1：
输入：nums = [12,345,2,6,7896] 输出：2 解释： 12 是 2 位数字（位数为偶数） 345 是 3 位数字（位数为奇数） 2 是 1 位数字（位数为奇数） 6 是 1 位数字 位数为奇数） 7896 是 4 位数字（位数为偶数） 因此只有 12 和 7896 是位数为偶数的数字 示例 2：
输入：nums = [555,901,482,1771] 输出：1 解释： 只有 1771 是位数为偶数的数字。
题解
方法一：暴力列举法
class Solution { public: int findNumbers(vector<int>& nums) { int d=0; for(int i=0;i<nums.size();i++){ if(nums[i]>9 && nums[i]<100 || nums[i]>999 && nums[i]<10000 || nums[i]==100000) d++; } return d; } }; 时间复杂度O(N)空间复杂度O(1)方法二：枚举+字符串
class Solution { public: int findNumbers(vector<int>& nums) { int ans = 0; for (int num: nums) { if (to_string(num).size() % 2 == 0) { ++ans; } } return ans; } };时间复杂度：O(N)，其中 N 是数组 nums 的长度。这里假设将整数转换为字符串的时间复杂度为 O(1)。
空间复杂度：O(1)
方法三：枚举+数学
class Solution{ public: int findNumbers(vector<int>& nums){ int ans = 0; for(int num: nums){ if((int)(log10(num)+1) % 2 == 0){ ++ans; } } return ans; } };时间复杂度：O(N)
空间复杂度：O(1)
问题
给你一个数组 arr ，请你将每个元素用它右边最大的元素替换，如果是最后一个元素，用 -1 替换。
完成所有替换操作后，请你返回这个数组。
示例：
输入：arr = [17,18,5,4,6,1] 输出：[18,6,6,6,1,-1]
提示：
1 <= arr.length <= 10^4 1 <= arr[i] <= 10^5
题解
逆序遍历
从数组右边倒着遍历
class Solution { public: vector<int> replaceElements(vector<int>& arr) { int max=-1; for(int i=arr.size()-1;i>=0;i--){ int tmp =max; if(arr[i]>max) max = arr[i]; arr[i] = tmp; } return arr; } }; //官方的程序更巧妙一点 class Solution { public: vector<int> replaceElements(vector<int>& arr) { int n = arr.size(); vector<int> ans(n); ans[n - 1] = -1; for (int i = n - 2; i >= 0; --i) { ans[i] = max(ans[i + 1], arr[i + 1]); } return ans; } }; 时间复杂度O(N)空间复杂度O(1) （对于官方的程序，复杂度不考虑返回数组所需的空间）问题
给你一个整数 n，请你返回 任意 一个由 n 个 各不相同 的整数组成的数组，并且这 n 个数相加和为 0 。
示例 1：
输入：n = 5 输出：[-7,-1,1,3,4] 解释：这些数组也是正确的 [-5,-1,1,2,3]，[-3,-1,2,-2,4]。 示例 2：
输入：n = 3 输出：[-1,0,1] 示例 3：
输入：n = 1 输出：[0]
提示：
1 <= n <= 1000
题解
n为偶数：正反数成对放回；n为奇数，加个0；
class Solution { public: vector<int> sumZero(int n) { vector<int> ans; if(n%2 == 0){ for(int i=1;i<=n/2;i++){ ans.push_back(i); ans.push_back(-i); } } else{ for(int i=1;i<=(n-1)/2;i++){ ans.push_back(i); ans.push_back(-i); } ans.push_back(0); } return ans; } }; 时间复杂度O(N)空间复杂度O(1) 不包括返回的ans占用的空间python美学
class Solution: def sumZero(self, n: int) -> List[int]: return range(1 - n, n, 2) 复杂度？？我不知道！！问题
给你一个数组 nums，对于其中每个元素 nums[i]，请你统计数组中比它小的所有数字的数目。
换而言之，对于每个 nums[i] 你必须计算出有效的 j 的数量，其中 j 满足 j != i 且 nums[j] < nums[i] 。
以数组形式返回答案。
示例 1：
输入：nums = [8,1,2,2,3] 输出：[4,0,1,1,3] 解释： 对于 nums[0]=8 存在四个比它小的数字：（1，2，2 和 3）。 对于 nums[1]=1 不存在比它小的数字。 对于 nums[2]=2 存在一个比它小的数字：（1）。 对于 nums[3]=2 存在一个比它小的数字：（1）。 对于 nums[4]=3 存在三个比它小的数字：（1，2 和 2）。 示例 2：
输入：nums = [6,5,4,8] 输出：[2,1,0,3] 示例 3：
输入：nums = [7,7,7,7] 输出：[0,0,0,0]
提示：
2 <= nums.length <= 500 0 <= nums[i] <= 100
题解
遍历
class Solution { public: vector<int> smallerNumbersThanCurrent(vector<int>& nums) { vector<int> result; for(int i=0;i<nums.size();i++){ int count = 0; for(int j=0;j<nums.size();j++){ if(nums[i]>nums[j]) count++; } result.push_back(count); } return result; } }; 时间复杂度O(N**2)空间复杂度O(1) 不包含返回的数组大小比较6的一个解法
很厉害，看代码就知道了
lass Solution(object): def smallerNumbersThanCurrent(self, nums): """ :type nums: List[int] :rtype: List[int] """ dic = [0]*101 for n in nums: dic[n] += 1 return [sum(dic[0:n]) for n in nums] 时间复杂度O(N)，实际上return那里，这种写法，时间复杂度可能为O(N**2)空间复杂度O(N) 不包含返回的数组大小好吧，上一个解法就是官方的解法
class Solution { public: vector<int> smallerNumbersThanCurrent(vector<int>& nums) { vector<int> cnt(101, 0); vector<int> vec((int)nums.size(), 0); for (int i = 0;i < (int)nums.size(); ++i){ cnt[nums[i]]++; } for (int i = 1;i <= 100; ++i) cnt[i] += cnt[i-1]; // 求前缀和 for (int i = 0;i < (int)nums.size(); ++i){ if (nums[i]) vec[i] = cnt[nums[i] - 1]; } return vec; } };时间复杂度：统计 cntcnt 数组的前缀和需要 O(S)的时间，遍历数组需要 O(n)的时间，所以总时间复杂度为 O(S+n) ，其中 S 为值域大小，n=nums.length 。
空间复杂度：O(S) ，需要开一个值域大小的数组
问题
给你两个整数数组 arr1 ， arr2 和一个整数 d ，请你返回两个数组之间的 距离值 。
「距离值」 定义为符合此距离要求的元素数目：对于元素 arr1[i] ，不存在任何元素 arr2[j] 满足 |arr1[i]-arr2[j]| <= d 。
示例 1：
输入：arr1 = [4,5,8], arr2 = [10,9,1,8], d = 2 输出：2 解释： 对于 arr1[0]=4 我们有： |4-10|=6 > d=2 |4-9|=5 > d=2 |4-1|=3 > d=2 |4-8|=4 > d=2 所以 arr1[0]=4 符合距离要求
对于 arr1[1]=5 我们有： |5-10|=5 > d=2 |5-9|=4 > d=2 |5-1|=4 > d=2 |5-8|=3 > d=2 所以 arr1[1]=5 也符合距离要求
对于 arr1[2]=8 我们有： |8-10|=2 <= d=2 |8-9|=1 <= d=2 |8-1|=7 > d=2 |8-8|=0 <= d=2 存在距离小于等于 2 的情况，不符合距离要求
故而只有 arr1[0]=4 和 arr1[1]=5 两个符合距离要求，距离值为 2 示例 2：
输入：arr1 = [1,4,2,3], arr2 = [-4,-3,6,10,20,30], d = 3 输出：2 示例 3：
输入：arr1 = [2,1,100,3], arr2 = [-5,-2,10,-3,7], d = 6 输出：1
提示：
1 <= arr1.length, arr2.length <= 500 -10^3 <= arr1[i], arr2[j] <= 10^3 0 <= d <= 100
题解
暴力遍历
class Solution { public: int findTheDistanceValue(vector<int>& arr1, vector<int>& arr2, int d) { int ans=0; for(int i:arr1){ int flag=0; for(int j:arr2){ if(abs(i-j)<=d){ flag=1; break; } } if(flag==0) ans++; } return ans; } }; //官方的还是简洁一点 class Solution { public: int findTheDistanceValue(vector<int>& arr1, vector<int>& arr2, int d) { int cnt = 0; for (auto &x: arr1) { bool ok = true; for (auto &y: arr2) { ok &= (abs(x - y) > d); } cnt += ok; } return cnt; } }; 时间复杂度O(N*M),N,M分别为两个数组的长度空间复杂度O(1)二分查找
要知道是否每一个 yj 是不是满足 |x_i - y_j| > d∣x i −y j∣>d，我们枚举了所有 y_jyj 。实际上我们只要找到大于等于 x_ix i的第一个 y_jy 和小于 xx 的第一个 y_jyj，看看它们满不满足这个性质就可以了。我们可以对 arr2 进行排序，然后对于 arr1 中的每个元素 x_ixi ，在 arr2 中二分寻找上述的两个 y_jyj，如果这两个元素满足性质，则所有元素都满足性质，将答案增加 11。
class Solution{ public: int findTheDistanceValue(vector<int>& arr1,vector<int>& arr2,int d){ sort(arr2.begin(),arr2.end()); int cnt = 0; for(auto &x: arr1){ unsigned p = lower_bound(arr2.begin(),arr2.end(),x)-arr2.begin(); bool ok = true; if(p<arr2.size()) ok &= (arr2[p]-x>d); if(p-1>=0 && p-1 <=arr2.size()) ok &= (x-arr2[p-1] >d); cnt += ok; } return cnt; } };假设 arr1 中元素个数为 n，arr2 中元素个数为 m。
时间复杂度：给 arr2 排序的时间代价是O(mlogm)，对于 arr1 中的每个元素都在 arr2 中二分的时间代价是 O(nlogm)，故渐进时间复杂度为O((n+m)logm)。
空间复杂度：这里没有使用任何的辅助空间，故渐进空间复杂度为 O(1)
问题
给你一个整数数组 nums，请你选择数组的两个不同下标 i 和 j，使 (nums[i]-1)*(nums[j]-1) 取得最大值。
请你计算并返回该式的最大值。
示例 1： 输入：nums = [3,4,5,2] 输出：12 解释：如果选择下标 i=1 和 j=2（下标从 0 开始），则可以获得最大值，(nums[1]-1)*(nums[2]-1) = (4-1)*(5-1) = 3*4 = 12 。提示：
2 <= nums.length <= 5001 <= nums[i] <= 10^3题解
排序后再求解的方法，额，鄙视！
没啥可说的方法
遍历找到两个不同下标的最大值，遍历了两次
class Solution { public: int maxProduct(vector<int>& nums) { int i=0; for(int k=0;k<nums.size();k++){ if(nums[k]>nums[i]) i=k; } int j=i==0?i+1:i-1; for(int k=0;k<nums.size();k++){ if(k==i) continue; if(nums[k]>nums[j]) j=k; } return (nums[i]-1)*(nums[j]-1); } }; 时间复杂度O(N)空间复杂度O(1)稍微升级版
遍历一次就够了
class Solution { public: int maxProduct(vector<int>& nums) { int max1=0,max2=0; for(int k=0;k<nums.size();k++){ if(nums[k]>max1){ max2 = max1; max1 = nums[k]; } else if(nums[k]>max2) max2 = nums[k]; } return (max1-1)*(max2-1); } }; 时间复杂度O(N)空间复杂度O(1)问题
给你一个数组 nums ，数组中有 2n 个元素，按 [x1,x2,…,xn,y1,y2,…,yn] 的格式排列。
请你将数组按 [x1,y1,x2,y2,…,xn,yn] 格式重新排列，返回重排后的数组。
示例 1：
输入：nums = [2,5,1,3,4,7], n = 3 输出：[2,3,5,4,1,7] 解释：由于 x1=2, x2=5, x3=1, y1=3, y2=4, y3=7 ，所以答案为 [2,3,5,4,1,7] 示例 2：
输入：nums = [1,2,3,4,4,3,2,1], n = 4 输出：[1,4,2,3,3,2,4,1] 示例 3：
输入：nums = [1,1,2,2], n = 2 输出：[1,2,1,2]
提示：
1 <= n <= 500 nums.length == 2n 1 <= nums[i] <= 10^3
题解
//形式一： class Solution { public: vector<int> shuffle(vector<int>& nums, int n) { vector<int> ans(2*n,0); for(int i=0;i<n;i++){ ans[2*i]=nums[i]; ans[2*i+1]=nums[i+n]; } return ans; } }; //形式二： class Solution { public: vector<int> shuffle(vector<int>& nums, int n) { vector<int> ans; for(int i=0;i<n;i++){ ans.push_back(nums[i]); ans.push_back(nums[i+n]); } return ans; } }; 时间复杂度O(N)空间复杂度O(1) 不包含返回的ans占用的空间python美学
class Solution: def shuffle(self,nums,n): nums[::2],nums[1::2]=nums[:n],nums[n:] return nums 复杂度？？？？？？？美就够了！！！问题给你两个整数，n 和 start 。
数组 nums 定义为：nums[i] = start + 2*i（下标从 0 开始）且 n == nums.length 。
请返回 nums 中所有元素按位异或（XOR）后得到的结果。
示例 1：
输入：n = 5, start = 0 输出：8 解释：数组 nums 为 [0, 2, 4, 6, 8]，其中 (0 ^ 2 ^ 4 ^ 6 ^ 8) = 8 。 “^” 为按位异或 XOR 运算符。 示例 2：
输入：n = 4, start = 3 输出：8 解释：数组 nums 为 [3, 5, 7, 9]，其中 (3 ^ 5 ^ 7 ^ 9) = 8. 示例 3：
输入：n = 1, start = 7 输出：7 示例 4：
输入：n = 10, start = 5 输出：2
提示：
1 <= n <= 1000 0 <= start <= 1000 n == nums.length
题解
class Solution { public: int xorOperation(int n, int start) { int ans = start; for(int i=1;i<n;i++){ start += 2; ans = ans^start; } return ans; } }; 时间复杂度O(N)空间复杂度O(1)O(1)解法
。。。。。。。。。。
。。。
对于 [1,k] 的连续整数的异或结果可以归结为 getXorResult(k) 通过简单归纳可知。
对于 k % 4 = 0, getXorResult(k) = k;对于 k % 4 = 1, getXorResult(k) = 1;对于 k % 4 = 2, getXorResult(k) = k + 1;对于 k % 4 = 3, getXorResult(k) = 0; 从而对于 [k1,k2] 的连续整数的异或结果为 getXorResult(k2) ^ getXorResult(k1 - 1)对于间隔为 2 的 [k1,k2] 非连续整数时，
对于 k1,k2 为偶数，可以由 [k1/2,k2/2] 的结果左移一位得到: getXorResult(k2 / 2)<<1 ^ getXorResult(k1 / 2 - 1)<<1
对于 k1,k2 为偶数，可以由 [k1/2,k2/2] 的结果左移一位，并且补上二进制最后一位 (start & n & 1): (getXorResult(k2 / 2) ^ getXorResult(k1 / 2 - 1))<<1
。。。。。。。 。。。。。。。。。。。。。 时间复杂度O(1)空间复杂度O(1)问题
给你一个数字数组 arr 。
如果一个数列中，任意相邻两项的差总等于同一个常数，那么这个数列就称为 等差数列 。
如果可以重新排列数组形成等差数列，请返回 true ；否则，返回 false 。
示例 1：
输入：arr = [3,5,1] 输出：true 解释：对数组重新排序得到 [1,3,5] 或者 [5,3,1] ，任意相邻两项的差分别为 2 或 -2 ，可以形成等差数列。 示例 2：
输入：arr = [1,2,4] 输出：false 解释：无法通过重新排序得到等差数列。
提示：
2 <= arr.length <= 1000 -10^6 <= arr[i] <= 10^6
题解
先排序。依次遍历比较差值
class Solution { public: bool canMakeArithmeticProgression(vector<int>& arr) { sort(arr.begin(),arr.end()); int diff = arr[0]-arr[1]; for(int i=0; i<arr.size()-1;i++){ if(arr[i]-arr[i+1] != diff) return false; } return true; } }; 时间复杂度O(n*logn) 排序时间代价为O(nlogn),遍历序列时间代价O(n),空间复杂度O(logn),快速排序使用的栈空间期望是O(logN)问题
给你一个整数数组 nums 。
如果一组数字 (i,j) 满足 nums[i] == nums[j] 且 i < j ，就可以认为这是一组 好数对 。
返回好数对的数目。
示例 1：
输入：nums = [1,2,3,1,1,3] 输出：4 解释：有 4 组好数对，分别是 (0,3), (0,4), (3,4), (2,5) ，下标从 0 开始 示例 2：
输入：nums = [1,1,1,1] 输出：6 解释：数组中的每组数字都是好数对 示例 3：
输入：nums = [1,2,3] 输出：0
提示：
1 <= nums.length <= 100 1 <= nums[i] <= 100
题解
数学
class Solution { public: int numIdenticalPairs(vector<int>& nums) { vector<int> cnt(100,0); for(auto i:nums) cnt[i-1]++; int ans=0; for(auto i : cnt){ ans += i*(i-1)/2; } return ans; } }; 时间复杂度O(N)空间复杂度O(N)官方版哈希表（我就是不会用）法
class Solution{ public: int numIdenticalPairs(vector<int>& nums){ unordered_map<int,int> m; for(int num: nums){ ++m[num]; } int ans = 0; for (const auto &[k,v] : m){ ans += v*(v-1)/2; } return ans; } } 时间复杂度：O(n)O(n)。空间复杂度：O(n)O(n)，即哈希表使用到的辅助空间的空间代价python暴力美学法
class Solution: def numIdenticalPairs(self,nums:List[int]) -> int: return sum([nums[inx+1:].conut(i) for inx,i in enumerate(nums)]) 时间复杂度O(N**2)空间复杂度O(N)