leetcode 双指针算法_双指针算法 leetcode

这两周刷了双指针算法的一些题目,列表如下：

4Sum

4SumII

3Sum Closest

Two Sum II - Input Array Is Sorted

3Sum Smaller

Valid Triangle Number

3Sum

核心思路都是用两个指针指向左右两端，然后往中间不停的靠近。直到指针相遇。

模板如下：

while(left < right)

{

if（)

left++;

else if

right--;

else{

left++;

right--;

}

}

而以上几个题目中也就是根据这个核心思路加以变形。

比如4 sum 和3 sum. 只要降低维度到 2 sum，就能解决问题。

而降低维度的办法也简单，用for 循环去把维度降低一个。比如3sum。

for循环固定一个数值，问题就降低为2sum了。

4sum的问题依然如此。

但是有个题目要单独谈一下， Valid triangle number

大家初中都学过，三角形的条件是两边之和大于第三边。并且每个边都要满足。

如果我们给了排序的数组{4， 4， 6，7，  8}

1. 先降低维度， 把3个边的问题边两个边。 这个好办，for循环一下。

2. 剩下的两个边，该从哪取值哪？

        一般取值也只有两个区间，第一个固定的点的左侧取值和右侧取值。

        比如for 循环到了6， 剩下的两个边是从6的左侧去还是右侧取那？

        如果从右侧取， 那么右侧的数值都比6 大，所以两个数的和（7+8）肯定大于6.

        你还得继续测试下其他任意两边和。

        所以从左侧取是最好的办法， 还是比如6。 从左边取数值4， 4 加起来为8.大于6. 

        并且任意一个4和6组合都大于另外一个4. 

        这就好比 a < b < c

        如果a+b>c, 那么b+c > a吗？ 或者a + c> b 吗？   那是肯定的啊！因为单独一个c都是大于a或者b的。

        这也是为何要固定c，其他的两边从c的左边取。

        向反如果固定a， 剩余的两边从右边取。

        a<b<c 如果b+c > a, 那么 a+b> c吗? 不一定，对不。

所以遇到问题可以用公式带入下看看。就能看到出题的人用的办法了。

我一直觉得出这些题目的应该都是数学比较不错的，太考验数学基础了。

代码如下

class Solution {
public:
    void ValidTriangleNumber(vector<int>& nums, int edge, int &ret, int left, int right) {
        
        while(left < right) {
            if(left < right && nums[left] + nums[right] > edge) {
                ret+=right-left;
                right--;
            }
            else if(left < right && nums[left] + nums[right] <= edge)
                left++;
        }
    }
    int triangleNumber(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int ret=0;
        
        for(int i =0;i<nums.size();i++){
            ValidTriangleNumber(nums, nums[i], ret,i+1,nums.size()-1);
        }
        
        return ret;
    }
};