697. 数组的度
给定一个非空且只包含非负数的整数数组 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范围内的整数。
第一版 自己写的，还行吧
执行用时 :48 ms, 在所有 cpp 提交中击败了72.42%的用户
内存消耗 :15.2 MB, 在所有 cpp 提交中击败了12.36%的用户
int findShortestSubArray(vector<int>& nums) { unordered_map<int, vector<int>> res;//val first出现的位序,last出现的位序 int span=0; for (size_t i = 0; i < nums.size(); ++i) { res[nums[i]].push_back(i); span = span > res[nums[i]].size() ? span : res[nums[i]].size(); } int minLen = nums.size(),temp; for (auto& r : res) { if (r.second.size() == span) { temp = r.second[r.second.size() - 1] - r.second[0]; minLen = minLen < temp ? minLen : temp; } } return minLen + 1; }
888. 公平的糖果交换
爱丽丝和鲍勃有不同大小的糖果棒：A[i] 是爱丽丝拥有的第 i 块糖的大小，B[j] 是鲍勃拥有的第 j 块糖的大小。
因为他们是朋友，所以他们想交换一个糖果棒，这样交换后，他们都有相同的糖果总量。（一个人拥有的糖果总量是他们拥有的糖果棒大小的总和。）
返回一个整数数组 ans，其中 ans[0] 是爱丽丝必须交换的糖果棒的大小，ans[1] 是 Bob 必须交换的糖果棒的大小。
如果有多个答案，你可以返回其中任何一个。保证答案存在。
示例 1：
输入：A = [1,1], B = [2,2]
输出：[1,2]
示例 2：
输入：A = [1,2], B = [2,3]
输出：[1,2]
示例 3：
输入：A = [2], B = [1,3]
输出：[2,3]
示例 4：
输入：A = [1,2,5], B = [2,4]
输出：[5,4]
提示：
1 <= A.length <= 100001 <= B.length <= 100001 <= A[i] <= 1000001 <= B[i] <= 100000- 保证爱丽丝与鲍勃的糖果总量不同。
- 答案肯定存在。
第一版，自己写的，执行这也太慢了
执行用时 :1224 ms, 在所有 cpp 提交中击败了14.22%的用户
内存消耗 :12 MB, 在所有 cpp 提交中击败了95.49%的用户
vector<int> fairCandySwap(vector<int>& A, vector<int>& B) { int sumA=0, sumB=0; for (auto& a : A) { sumA += a; } for (auto& b : B) { sumB += b; } int temp = sumA - sumB > 0 ? sumA - sumB : sumB - sumA; temp = temp / 2; for (auto& a : A) { for (auto& b : B) { if (a - b == temp || b - a == temp) { if(sumA - a + b == sumB - b + a) return { a,b }; } } } return { 0,0 }; }
第二版，改进了一下，加一个二分查找，快多了
执行用时 :132 ms, 在所有 cpp 提交中击败了88.39%的用户
内存消耗 :12.2 MB, 在所有 cpp 提交中击败了83.46%的用户
vector<int> fairCandySwap(vector<int>& A, vector<int>& B) { int sumA=0, sumB=0; for (auto& a : A) { sumA += a; } for (auto& b : B) { sumB += b; } int b=0,temp = sumA - sumB > 0 ? sumA - sumB : sumB - sumA; temp = temp / 2; sort(A.begin(), A.end()); sort(B.begin(), B.end()); for (auto& a : A) { if (lower_bound(B.begin(),B.end(),a + temp)!=B.end()) { b = *(lower_bound(B.begin(), B.end(), a + temp)); if(sumA - a + b == sumB - b + a) return { a,b }; } if (lower_bound(B.begin(), B.end(), a - temp) != B.end()) { b = *(lower_bound(B.begin(), B.end(), a - temp)); if (sumA - a + b == sumB - b + a) return { a,b }; } } return { 0,0 }; }
