题解 | #数组中相加和为0的三元组#

C++版本3种方法 ，循序渐进

// NC128容器盛水问题
class Solution {
public:
    /**
     * max water
     * @param arr int整型vector the array
     * @return long长整型
     */
    long long maxWater(vector<int>& arr) {

    /*     法1------------【超时】---------------------
        每个位置能盛的水由左右的最大值中最小值决定（木桶原理）
        该方法是累加每个位置的水量
        时间复杂度：O(N^2),遍历每个位置O(n)，针对每个位置求左右侧的最值O(n)，空间O(1)
    */    

        int  len=arr.size();
        if(len<3) return 0;

        long long ret=0;
        //遍历每个位置,第一和最后一个位置不用遍历
        for(int i=1;i<len-1;++i){
            int leftmax=0;
            int rightmax=0;
            //找到i左侧的最大值
            for(int left=0;left<i;++left){
                leftmax=max(leftmax,arr[left]);
            }
            //找到i右侧的最大值
            for(int right=i+1;right<len;++right){
                rightmax=max(rightmax,arr[right]);
            }
            //累加
            ret += max( min(leftmax,rightmax)-arr[i] , 0 );
        }
     return ret;


     // 法2-----------------------------------------------
     // 每次遍历比较麻烦，遍历一次，用2个数组保存每个位置左右侧的最值，再累加
        int  len = arr.size();
        if(len<3) return 0;

        long long ret = 0;
        int leftmax[len];
        int rightmax[len];
        leftmax[0]=0;
        rightmax[len-1]=0;
        //leftmax[i]表示arr[0...i-1]的最大值，如果本身最大，那最大值就是自身
        for(int i=1; i<len; ++i){
            leftmax[i] = max( leftmax[i-1] , arr[i-1] );
        }
        //rightmax[i]表示arr[i+1...len-1]的最大值，如果本身最大，那最大值就是自身
        for(int i=len-2;i>=0;--i){
            rightmax[i] = max( rightmax[i+1] , arr[i+1] );
        }
        //累加,对于任意一个位置，左侧的最大值为leftmax[i],右侧为rightmax[i];
        for(int i=1;i<len-1;++i){
            ret+= max( min( leftmax[i],rightmax[i] ) - arr[i] , 0    );
        }
        return ret;
    /*         
        法3--------------------------------
        左右指针 左右指针分别从第2和倒数第2位置开始
        leftmax:arr[0...i-1]的最大值
        rightmax表示arr[i+1...len-1]之间的最大值

        如果leftmax<=rightmax 那么可以求出【i】位置的是max(leftmax -arr[i],0);
        因为：右指针从右往左走，i和右指针中间的位置虽然没有遍历，但是这些位置的rightmax一定>=当前rightmax，所以可以求

        如果leftmax>rightmax，那么可以求出【len-2】位置的是max(right-arr[i],0);

        当左右指针相遇【之后】，就退出
        会不会只求了一半？
            不会，当leftmax<=rightmax 时候，可以确定左指针位置可以求，因为左指针右边未遍历区域的max不会小于当前rightmax
            右指针位置的水量在leftmax>rightmaxd的时候，可以求，水量算多少取决于短板rihgmax大小
            因为当leftmax>rightmax后，后续的leftmax不会小于当前的leftmax.
     */    
        int  len = arr.size();
        if(len<3) return 0;

        long long ret = 0;
        int left=1;//左指针
        int right=len-2;
        int leftmax=arr[0];//位置【i】左侧的最大值
        int rightmax=arr[len-1];
        while(left<=right){
            if(leftmax<=rightmax){
                ret += max( leftmax-arr[left] , 0 ); 
                leftmax=max(leftmax,arr[left++]);//更新leftmax，为下一个位置做准备
            }else{
                ret += max( rightmax - arr[right] , 0 );
                rightmax = max( rightmax, arr[right--] );
            }

        }
        return ret;

    }
};