【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;
    }