leetcode2-双指针

利用两个下标/迭代器控制遍历范围从而降低枚举复杂度的方法。双指针│├── ① 相向双指针│ ││ ├── 两数之和│ ├── 回文│ ├── 盛最多水的容器│ └── 三数之和│├── ② 同向双指针│ ││ ├── 快慢指针│ ├── 删除重复元素│ ├── 移动零│ └── 移除元素│└── ③ 滑动窗口│├── 最长/最短子数组├── 最长无重复子串└── 满足条件的连续区间相比嵌套循环双指针通过规律跳过一些不需要遍历的点可以降低时间复杂度;信号是当多重循环结构中若存在有些点在一定条件下不需要被遍历则存在双指针优化。我明白可以跳过遍历一些点但是要是不遍历检查这些点怎么知道这个点满足跳过遍历的条件呢t2暴力双循环解法显然当数据量多时存在超时问题需要双指针加速class Solution { public: int maxArea(vectorint height) { int max 0, d, h; int r height.size(); for (int l 0; l r; l) { for (int j r - 1; j l; j--) { if (h min(height[j], height[l])) { d j - l; h min(height[j], height[l]); if (max (h * d)) { max h * d; } } } } return max; } };这版本已经加上了跳过条件当右边界高度等于左边界高度时即停止但是无奈还是超时555class Solution { public: int maxArea(vectorint height) { int max 0, d,h; int r height.size(); for (int l 0; l r; l) { for (int j r - 1; j l; j--) { d j - l; h min(height[j],height[l]); if (max h * d) { max h * d; } if (height[j] height[l]) { break; } } } return max; } };改成大于等于判断条件然后每次内循环右边界从上次停止处开始可以通过lc提交但仍非双指针双指针左右交替一步一步向内缩我的方法是向右遍历i在j上做剪枝处理确实是少了一边。class Solution { public: int maxArea(vectorint height) { int max 0, d, h, s; int r height.size(); s r-1; for (int l 0; l r; l) { for (int j s; j l; j--) { d j - l; h min(height[j], height[l]); if (max h * d) { max h * d; } if (height[j] height[l]) { s j; break; } } } return max; } };t3依旧不会双指针依旧双循环超时class Solution { public: vectorvectorint threeSum(vectorint nums) { int need 0; int r nums.size(); unordered_mapint, int mp, cmp; setvectorint s; sort(nums.begin(), nums.end()); for (int i 0; i r; i) { cmp[nums[i]]; } for (int i 0; i r; i) { for (int ri r - 1; ri i; ri--) { mp cmp; need -nums[i] - nums[ri]; mp[nums[i]]--; mp[nums[ri]]--; if (mp[need] 0) { vectorint temp { nums[i], nums[ri], need }; sort(temp.begin(), temp.end()); s.insert(temp); } } } return vectorvectorint(s.begin(), s.end()); } };