153. 寻找旋转排序数组中的最小值
假设按照升序排序的数组在预先未知的某个点上进行了旋转。没有想象中的难
( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。
请找出其中最小的元素。
你可以假设数组中不存在重复元素。
示例 1:
输入: [3,4,5,1,2]输出: 1示例 2:
输入: [4,5,6,7,0,1,2]输出: 0
intfindMin(vector<int>&nums) {
if (nums.size() ==1||nums[0]<nums[nums.size()-1]) returnnums[0];
inthigh=nums.size() -1;
while(nums[high]<nums[0])
{
high--;
}
++high;
returnnums[high];
}
454. 四数相加 II
给定四个包含整数的数组列表 A , B , C , D ,计算有多少个元组 (i, j, k, l) ，使得 A[i] + B[j] + C[k] + D[l] = 0。
为了使问题简单化，所有的 A, B, C, D 具有相同的长度 N，且 0 ≤ N ≤ 500 。所有整数的范围在 -228 到 228 - 1 之间，最终结果不会超过 231 - 1 。
例如:
输入:A = [ 1, 2]B = [-2,-1]C = [-1, 2]D = [ 0, 2]
输出:2
解释:两个元组如下:
- (0, 0, 0, 1) -> A[0] + B[0] + C[0] + D[1] = 1 + (-2) + (-1) + 2 = 0
- (1, 1, 0, 0) -> A[1] + B[1] + C[0] + D[0] = 2 + (-1) + (-1) + 0 = 0
思路：建立一个哈希映射，一个记录AB数组的组合和，和为key，出现的次数为value计算CD数组的组合和，得到相反数，若该数存在于key中，即符合要求，将答案加上AB组合和中该数出现的次数(value)
第一版，使用map
intfourSumCount(vector<int>&A, vector<int>&B, vector<int>&C, vector<int>&D) {
intnum=0,temp=0;
map<int, int> sum_map;
for (autoa : A) {
for (autob : B) {
if (sum_map.count(a+b) ==0) sum_map[a+b] =1;
else
++sum_map[a+b];
}
}
for (autoc : C) {
for (autod : D) {
temp=-(c+d);
if (sum_map.count(temp)) num+=sum_map[temp];
}
}
returnnum;
}
执行用时 :492 ms, 在所有 C++ 提交中击败了42.54%的用户
内存消耗 :29.3 MB, 在所有 C++ 提交中击败了57.21%的用户
第二版 ，unordered_map
intnum=0,temp=0;
unordered_map<int, int> sum_map;
for (autoa : A) {
for (autob : B) {
if (sum_map.count(a+b) ==0) sum_map[a+b] =1;
else
++sum_map[a+b];
}
}
for (autoc : C) {
for (autod : D) {
temp=-(c+d);
if (sum_map.count(temp)) num+=sum_map[temp];
}
}
returnnum;
执行用时 :1822 ms, 在所有 C++ 提交中击败了98.56%的用户
内存消耗 :28.4 MB, 在所有 C++ 提交中击败了57.21%的用户
我的博客即将同步至腾讯云开发者社区，邀请大家一同入驻：https://cloud.tencent.com/developer/support-plan?invite_code=kgzy88yxhhom
