盛水最多的容器

（1）暴力解法

??算法思路：我們枚舉出所有的容器大小，取最大值即可。

??容器容積的計算方式：

??設(shè)兩指針 i , j ，分別指向水槽板的最左端以及最右端，此時容器的寬度為 j - i 。由于容器的高度由兩板中的較短的板決定，因此可得容積公式 ：
v = (j - i) * min( height[i] , height[j] );

class Solution {
public:
    int maxArea(vector<int>& height) {
        int n=height.size();
        int ret=0;
        //枚舉出所有的容器大小
        for(int i=0;i<n;i++)
        {
            for(int j=i+1;j<n;j++)
            {
                //計算當(dāng)前的容器容量
                int v=(j-i)*(min(height[i],height[j]));
                ret=max(ret,v);//取最大容量的容器
            }
        }
        return ret;
    }
};

??當(dāng)然由于兩次遍歷數(shù)組，所以時間復(fù)雜度為O(N²)，會超時。

?
（2）對撞指針

??算法思路：我們設(shè)置兩個指針left、right分別指向容器的兩個端點(diǎn)（因為這里的是數(shù)組，數(shù)組在內(nèi)存中的儲存是連續(xù)的，而且數(shù)組是通過它們的下表訪問，所有我們可以把數(shù)組下標(biāo)看成是指針進(jìn)行操作）不斷修改左右的端點(diǎn)來獲得容器的最大容量。

??容器的左邊界為 height[left] ，右邊界為 height[right] 。

??我們假設(shè)「左邊邊界」小于「右邊邊界」。

??水的容積會有如下變化形式：

??首先容器的寬度?定變小。由于左邊界較小，決定了水的高度。如果改變左邊界，新的水面高度不確定，但是?定不會超過右邊的柱子高度，因此容器的容積可能會增大或者減小。

??但是如果改變右邊界，無論右邊界移動到哪?，新的水面的高度?定不會超過左邊界，也就是現(xiàn)在左邊界的所在的水面高度，但是由于容器的寬度減小，因此容器的容積一定會變小。

??綜上，我們不斷選取左右兩個邊界中的較大邊界，以保留當(dāng)下的最有解，不斷的 left++ 或right–，直到left和right相遇。

class Solution {
public:
    int maxArea(vector<int>& height) {
        int left=0;
        int right=height.size()-1;
        int ret=0;
        //循環(huán)條件為右邊界大于左邊界
        while(left<right)
        {
            //計算當(dāng)前容器的容量
            int v=(right-left)*(min(height[left],height[right]));
            ret=max(v,ret);//不斷更新容器的最大容量
            if(height[left]>height[right]) right--;//不斷更新左右高度
            else left++;                           //保留高的，舍棄較矮的高
        }
        return ret;
    }
};

時間復(fù)雜度：O(N)

?
?

和為s的兩個數(shù)字

??和兩數(shù)之和不同的是，該數(shù)組中的元素是有序的，而且使用暴力解法會超時。

（1）對撞指針

這里有三種情況：

??當(dāng) nums[left] + nums[right] == target時，說明找到結(jié)果，記錄結(jié)果，并且返回；

??當(dāng) nums[left] + nums[right] < target 時，此時 nums[right] 相當(dāng)于是 nums[left] 能碰到的最大值。如果此時不符合要求，說明我們需要增加這兩個數(shù)之和，所以我們讓left++，再取更大的數(shù)，以來靠近我們的目標(biāo)和。

??當(dāng) nums[left] + nums[right] > target 時，說明我們所取的兩數(shù)較大，所以我們應(yīng)該減小這兩個數(shù)之和，讓right–，以此使得兩數(shù)的總和變小，以此來靠近我們的目標(biāo)和。不斷比較下?組數(shù)據(jù)，直至兩數(shù)和和目標(biāo)和相等。

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        int left=0;
        int right=nums.size()-1;
        while(left<right)
        {
            //如果兩數(shù)和等于目標(biāo)值，直接返回
            if(nums[left]+nums[right]==target)
            {
                return {nums[left],nums[right]};
            }//如果兩數(shù)和大于目標(biāo)值，right--
            else if(nums[left]+nums[right]>target)
            {
                right--;
            }//如果兩數(shù)和小于目標(biāo)值，left++    
            else
            {
                left++;
            }
        }
        //照顧編譯器，返回一個不存在的數(shù)組
        return {-1141514};
    }
};

時間復(fù)雜度：O(N)
文章來源地址http://www.zghlxwxcb.cn/news/detail-641949.html

到了這里，關(guān)于【算法】雙指針——leetcode盛最多水的容器、劍指Offer57和為s的兩個數(shù)字的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！