双指针
（1）三数之和问题（15，16）、四数之和问题（18）
解决思路：选定起点，使用排序+双指针的做法
解决难点：怎么排除重复项目：直接进入下一循环，如果值与上一个相等，则直接跳过，对于四个元素都是如此
扩展问题：四数之和（18）：在三数之和上加一个循环
（2）删除链表倒数第N个节点（19）
解决思路：使用双指针，一个置于第N(label = n - 1)个节点，另一个置于第1(label = 0)个，之后一起循环，直至后面一个节点循环至NULL处；
摩尔投票法
问题：选择数组中超过一定数量的数字的集合（LeetCode#229）
基本思路：使用比较抵消法，选取一个候选人，依次向后比较，如果不相同的话，则在原来的计数基础上抵消一个1，在所有的票数都被抵消后，则考虑更换候选人；候选人数目根据最多可能的结果来确定。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
| vector<int> majorityElement(vector<int>& nums){
int n = nums.size();
vector<int> ans;
int candiate1 = 0, cnt1 = 0, candiate2 = 0, cnt2 = 0;
for (int i = 0; i < n; ++i){
if(nums[i] == candiate1) cnt1++;
else if(nums[i] == candiate2) cnt2++:
else if(cnt1 == 0){
candiate1 = nums[i];
cnt1 = 1;
}else if(cnt2 == 0){
candiate2 = nums[i];
cnt2 = 1;
}else{
cnt1--, cnt2--;
}
}
cnt1 = cnt2 = 0;
for (auto i: nums){
if(i == candiate1) cnt1++;
else if(i == candiate2) cnt2++;
}
if(cnt1 > n/3) ans.push_back(candiate1);
if(cnt2 > n/3) ans.push_back(candiate2);
return ans;
}
|
一定要记住，hash表初始的value是0！！！
This is copyright.