leetcode(hot100)6、7

解题思路：先排序再利用双指针思想然后再去重处理。去重要 nums [i] == nums [i- 1 ] 考虑-1，-1，2这种情况。

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        sort(nums.begin(),nums.end());
        vector<vector<int>>result;
        for(int i = 0;i<nums.size();i++){
            if(nums[i] > 0)return result;
            if(i>0 && nums[i] == nums[i-1])continue;
            int left = i+1,right = nums.size()-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]});
                    right--;
                    left++;
                    while(left < right && nums[right] == nums[right+1])right--;
                    while(left<right && nums[left] == nums[left-1])left++;
                }

            }

        }
        return result;
    }
};

解题思路：

当前能接住的雨水=min(左侧最高,右侧最高)−当前高度 可以理解为能储水的体积 是哪一侧的最高高度然后减去当前高度

利用双指针不断向中间移动，然后通过动态更新leftmax和rightmax，当左指针最大高度小于右指针最大高度就左移反之就右移。能够存储的雨水量是一侧得到的最大高度减去当前的高度。能存储雨水的一定是短板而不是长板所以长板可以忽略不计。

利用哪一侧高度低哪一侧指针去移动。为什么只比较 leftmax 和 rightmax：

• 如果 leftmax < rightmax，说明左侧的高度限制了雨水量，右侧高度足够高，可以忽略右侧的影响。

• 反之，右侧高度限制了雨水量，忽略左侧的影响。

移动较小的一边是因为：

1. 当前柱子的储水量取决于较小的一边。

2. 较大的一边还有可能影响后续柱子的储水量，所以暂时不移动。

   class Solution {
   public:
       int trap(vector<int>& height) {
           int left = 0,right = height.size()-1,sum = 0;
           int leftmax=0,rightmax=0;
           while(left < right){
               leftmax = max(leftmax,height[left]);
               rightmax = max(rightmax,height[right]);
               if(leftmax < rightmax){
                   sum += leftmax-height[left];
                   left++;
               }
               else{
                   sum += rightmax-height[right];
                   right--;
               }
           }
           return sum;
           
       }
   };