【LeetCode 热题 100】双指针 系列

📁283. 移动零

        对于该题目，需要注意的是两个地方，一是保持非零元素的相对顺序，以及O(1)的空间复杂度。

        采用双指针的思路，将数组划分成3个区间,。

[0 , left]：该区间内元素全是非零元素。

[left+1 , right]：该区间内元素全是零元素。

[right , n]：还没有遍历到的元素，未知。

        left：非零区间的左端点。初始化为-1，表示没有元素。

        right: 当前遍历到的元素的下标。

void moveZeroes(vector<int>& nums) {int left = -1 , right = 0;while(right < nums.size()){if(nums[right] != 0)swap(nums[++left] , nums[right]);++right;}}

📁11. 盛最多水的容器

        核心思想：将长度固定,然后从大到小枚举, 每次使用两边较小的高度,使用完后淘汰高度较小值。

int maxArea(vector<int>& height) {int ans = 0;int left = 0 , right = height.size() - 1;while(left < right){ans = max(ans , (right - left) * min(height[left] , height[right]));if(height[left] < height[right])++left;else--right;}return ans;}

📁15. 三数之和

        因为原数组是无序的，所以我们首先要对数组进行排序，方便我们使用双指针。

        我们从前往后枚举每个数，然后从该数后面通过双指针找到两个数，满足 nums[i] + nums[left] + nums[right] == 0。因为我们进行了排序，因此nums[left]、nums[right]都大于等于nums[i]，如果nums[i] > 0 ，就可以不用在遍历后面的数了，因为没有结果了。

        

vector<vector<int>> threeSum(vector<int>& nums) {sort(nums.begin() , nums.end());vector<vector<int>> ans;int i = 0;int n = nums.size();while(i < n){if(nums[i] > 0)break;int left = i + 1 , right = n - 1;while(left < right){if(nums[i] + nums[left] + nums[right] == 0){ans.push_back({nums[i] , nums[left++] , nums[right--]});while(left < right && nums[left] == nums[left - 1])++left;while(left < right && nums[right] == nums[right + 1])--right;}else if(nums[i] + nums[left] + nums[right] > 0)--right;else    ++left;}++i;while(i < n && nums[i] == nums[i-1])++i;}return ans;}

📁42. 接雨水

        我们采用双指针的算法，记录下来左右两侧最高的列（木桶原理），然后取出列能存储的雨水量，求和就是结果。

int trap(vector<int>& height) {int left = 0 , right = height.size() - 1;int leftMax = height[left] , rightMax = height[right];int ans = 0;while(left < right){leftMax = max(leftMax , height[left]);rightMax = max(rightMax , height[right]);if(leftMax < rightMax){//木桶原理，能接多少水取决于左边较低的列ans += (leftMax - height[left]);++left;}else{//木桶原理，能接多少水取决于右边较低的列ans += (rightMax - height[right]);--right;}}return ans;}