双指针算法

 一、

双指针指的是在遍历对象的过程中，不是普通的使用单个指针进行访问，而是使用两个指针（特殊情况甚至可以多个），两个指针或是同方向访问两个链表、或是同方向访问一个链表（快慢指针）、或是相反方向扫描（对撞指针），从而达到我们需要的目的。

 和为S的两个数字

比如说这道题 ，可以考虑使用双指针，题目说了，这是一个升序数组，那么我们可以考虑将一个指针i指向数组的第一个元素，将一个指针j指向数组的最后一个元素。

当i指向的元素+j指向的元素大于目标值的时候，说明j指向的值太大了，j--；当小于目标值的时候，说明i指向的值太小了，需要++。i与j相交后，没有找到目标值，说明不存在这样的数字。

class Solution {
public:
    vector<int> FindNumbersWithSum(vector<int> array,int sum) {
        int n = array.size();
        int i = 0;
        int j = n - 1;
        while (i < j)
        {
            if (array[i] + array[j] < sum)
            {
                i++;
            }
            else if (array[i] + array[j] > sum)
            {
                j--;
            }
            else 
            {
                return vector<int>{array[i], array[j]};
            }
        }
        return vector<int>();
    }
};

二、

有效三角形的个数

大眼一看，直接三个for循环暴力找答案。

class Solution {
public:

    bool check(int a, int b, int c)
    {
        return a + b > c && a + c > b && b + c > a;
    }


    int triangleNumber(vector<int>& nums) {
        int ans = 0;
        int n = nums.size();
        for (int i = 0; i < n; i++)
        {
            for (int j = i + 1; j < n; j++)
            {
                for (int k = j + 1; k < n; k++)
                {
                    if (check(nums[i], nums[j], nums[k]))
                    {
                        ans++;
                    }
                }
            }
        }

        return ans;

    }
};

 超时完全在意料之中。这个时候可以考虑把后两层循环优化成一层循环。这样时间复杂度就从n三方到n方了。

这个时候要思考，如何优化呢？

观察数组，是无序的，如果我们先排序，就可以少判断两次了。

如果是升序a < b < c， 只需要判断 a + b > c即可，因为a + c或者b+ c一定比另一个大，这样就减少了两次判断。

在想一下，如果我们先固定一个数字i，然后在区间l~r中判断有多少符合题目的三角形不就好了？确实可以。

我们先将最大的数字固定，然后在2~6这个区间进行判断。

如果说l + r > i，说明可以组成三角形，同时也说明比i大，比r小的数字也就是l~r区间的数字也可以与i组成三角形，将这些符合的三角形统计起来，并将r向左移动，继续对l + r 是否 > i进行判断，如果符合继续将r向左移动，反之将l向右移动。

AC代码

class Solution {
public:

    bool judge(int a, int b, int c)
    {
        return a + b > c;
    }

    int triangleNumber(vector<int>& nums) {
        if (nums.size() < 3) return 0;
        sort(nums.begin(), nums.end());
        int ans = 0;    
        for (int i = nums.size() - 1; i >= 2; i--)
        {
            int l =  0, r = i - 1;
            while (l < r)
            {
                if (judge(nums[l], nums[r], nums[i]))
                {
                    ans += r - l;
                    r--;
                }
                else 
                {
                    l++;
                }                
                
            }
        }

        return ans;

    }
};