哈希
1.两数之和（unordered_map）
给定一个整数数组 nums 和一个整数目标值 target,返回满足条件的数组下标
思路：用umap，一边遍历，一边装；
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int,int> umap;
vector<int> result;
for(int i = 0; i < nums.size(); i++) {
if(umap.find(target-nums[i]) != umap.end()) {
result.push_back(i);
result.push_back(umap[target-nums[i]]);
}
umap[nums[i]] = i;
}
return result;
}
};
|
49.字母异位词分组
思路：每次遍历前，先排序，然后用unordered_map<string, vector string>> mp的形式装
class Solution {
public:
vector<vector<string>> groupAnagrams(vector<string>& strs) {
vector<vector<string>> result;
unordered_map<string, vector<string>> mp;
for(int i = 0; i < strs.size(); i++) {
string s = strs[i];
sort(s.begin(), s.end());
mp[s].push_back(strs[i]);
}
for(auto it = mp.begin(); it != mp.end(); it++) {
result.push_back(it->second);
}
return result;
}
};
|
128. 最长连续序列*
给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。O(n)
思路：用uset装下数组元素，然后遍历数组元素，确保num-1不在uset中，就开始计算当前num在数组中的数字连续的最长子序列
class Solution {
public:
int longestConsecutive(vector<int>& nums) {
if(nums.size() == 0) return 0;
unordered_set<int> uset(nums.begin(), nums.end());
int longestRes = 0;
for(int num : uset) {
if(uset.find(num - 1) == uset.end()) {
int curnum = num;
int countLen = 1;
while(uset.find(curnum + 1) != uset.end()){
curnum++;
countLen++;
}
longestRes = max(longestRes, countLen);
}
}
return longestRes;
}
};
|
双指针
283.移动零
给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
思路：用两个指针l和r，r不停向前遍历，而l只有当r！= 0 时才++，最后补零即可；
class Solution {
public:
void moveZeroes(vector<int>& nums) {
int leftIndex = 0;
for(int rightIndex = 0; rightIndex < nums.size(); rightIndex++) {
if(nums[rightIndex] != 0) {
nums[leftIndex++] = nums[rightIndex];
}
}
for(;leftIndex < nums.size(); leftIndex++) {
nums[leftIndex] = 0;
}
}
};
|
11. 盛最多水的容器
给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。返回容器可以储存的最大水量。
思路：注意此处用双指针按列计算，求最大，那就从行最宽或者列最高着手，此处是行最宽开始
class Solution {
public:
int maxArea(vector<int>& height) {
int n = height.size();
int left = 0;
int right = n - 1;
int res = 0;
while(left < right) {
int ans = (right - left) * min(height[left], height[right]);
res = max(res, ans);
height[left] > height[right] ? right-- : left++;
}
return res;
}
};
|
15. 三数之和
给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。
思路：先排序，然后遍历数组，注意去重num[i-1] == num[i]就continue。再设置左右指针指向第二和第三个元素，>0 则左移右指针，<0则右移左值针，==0则加入res，然后注意左右指针移动的去重；
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>> result;
sort(nums.begin(), nums.end());
int n = nums.size();
for(int i = 0; i < n; i++) {
if(nums[i] > 0) return result;
if(i > 0 && nums[i] == nums[i - 1]) continue;
int left = i + 1, right = n - 1;
while(left < right) {
if(nums[i] + nums[left] + nums[right] > 0) right--;
else if(nums[i] + nums[left] + nums[right] < 0) left++;
else{
result.push_back(vector<int>{nums[i], nums[left],nums[right]});
while(left < right && nums[left] == nums[left+1]) left++;
while(left < right && nums[right] == nums[right-1]) right--;
right--;
left++;
}
}
}
return result;
}
};
|
42 接雨水
思路：构建左右指针数组left[n],right[n]，存当前元素（包含当前元素）左（右）边的最大值，然后遍历数组nums，找左右两边的最小值求和；
class Solution {
public:
int trap(vector<int>& height) {
if(height.size() <= 2) return 0;
vector<int> leftMax(height.size(), 0);
vector<int> rightMax(height.size(), 0);
int size = height.size();
leftMax[0] = height[0];
for(int i = 1; i < size; i++) {
leftMax[i] = max(leftMax[i - 1], height[i]);
}
rightMax[size - 1] = height[size - 1];
for(int i = size-2; i > 0; i--) {
rightMax[i] = max(rightMax[i + 1], height[i]);
}
int sum = 0;
for(int i = 0; i < size; i++) {
int count = min(leftMax[i], rightMax[i])-height[i];
if(count > 0) sum += count;
}
return sum;
}
};
|
