算法1--双指针

双指针

这里的指针不应仅仅理解为指针，其也可以是数组下标，还可以直接是数据本身，只要其可以在当前唯一找到对应数据。其一般用于对线性存储的数据（如数组）或数据读取时具有线性的问题进行求解，常见的双指针有2种形式：对撞指针和快慢指针，其中快慢指针一般用于出现循环的问题中。

经典例题

移动零

采用2个下标pos1=0和pos2=0，pos1指针不动，pos2指针向后遍历，遇到0就跳过，遇到非零元素就交换pos1和pos2下标的元素，同时++pos1。

class Solution {
public:
    void moveZeroes(vector<int>& nums) 
    {
        int pos1=0;
        int pos2=0;
        while(pos2<nums.size())
        {
            if(0!=nums[pos1])
            {
                ++pos1;
            }
            if(pos1<pos2&&0!=nums[pos2])
            {
                swap(nums[pos1],nums[pos2]);
                ++pos1;
            }
            ++pos2;
        }
    }
};

复写零

找到最后会被移动到数组末尾的元素的下标pos1，同时令pos2指向数组末尾元素，pos1从后往前遍历数组，遇到非零元素直接将该元素拷贝到pos2位置，同时–pos2，如果pos1遇到0，就将2个零写到pos2当前其前一个位置上，同时pos2减2.

class Solution {
public:
    void duplicateZeros(vector<int>& arr) 
    {
    	//寻找最后会被移动到数组末尾的元素的下标
        int left=-1;
        int right=-1;
        while(right+1<arr.size())
        {
            ++left;
            ++right;
            if(0==arr[left])
            {
                ++right;
            }
        }
        if(right+1>arr.size())
        {
            arr[--right]=0;
            --left;
            --right;
        }
		
		//遍历数组进行复写
        while(left>=0)
        {
            if(0==arr[left])
            {
                arr[right--]=0;
            }
            swap(arr[left--],arr[right--]);
        }
    }
};

快乐数

由于给定一个int型数字，其各位的平方和一定有一个最大值（不会超过int最大值，可以自己验证）和一个最小值0，即数字的各位的平方和得到的数据的个数是有限的，如果我们不停的将数字的各位进行平方和操作，其一定会出现2个相同的数据，即对数据的平方和操作一定是存在循环的，因此可以使用快慢指针解决问题

class Solution {
public:
    int DestructNum(int num)
    {
        int ret=0;
        while(num)
        {
            ret+=(num%10)*(num%10);
            num/=10;
        }

        return ret;
    }

    bool isHappy(int n) 
    {
        int slow=n;
        int fast=n;
        do
        {
            slow=DestructNum(slow);
            fast=DestructNum(fast);
            fast=DestructNum(fast);
        }
        while(fast!=slow&&slow!=1);
        if(1==slow)
        {
            return true;
        }

        return false;
    }
};

盛水最多的容器

left指向数组第一个元素，right指向数组末尾元素，计算得到一个容积v1，假设当前left是left和right中组数数据较小的下标。
如果固定left不动，让right–：①right对应的数组的值大于等于right之前的值，由于容器的容积取决于短边left，此时容器的宽度又减少了，故得到的容积一定比v1小；②如果right对应的数组的值小于right之前的值，容器的宽度和高度都减小了，故容器容器也一定比v1小。综上，让较大边right移动，其得到的容积一定比v1小。
因此我们应该移动小边left和right中的较小边，直至left和right相撞，过程中得到的容积一一比较即可得到最大容积。

class Solution {
public:
    int maxArea(vector<int>& height) 
    {
        int max_capacity=0;
        int left=0;
        int right=height.size()-1;
        while(left<right)
        {
            int min_height=height[left];
            if(min_height>height[right])
            {
                min_height=height[right];
            }
            int cur_capacity=min_height*(right-left);
            if(max_capacity<cur_capacity)
            {
                max_capacity=cur_capacity;
            }
            if(height[left]<height[right])
            {
                ++left;
            }
            else
            {
                --right;
            }
        }

        return max_capacity;
    }
};

有效三角形个数

将数据进行排序，使数据具有单调性，采用定一移二，将最大边pos3指向组数末尾，边pos1=0，边pos2=pos3-1。
如果arr[pos1]+arr[pos2]>arr[pos3]，那么pos1右边的元素加上arr[pos2]一定大于arr[pos3]，此时可以直接计算出当前可以获得的三角形的个数，接着–pos2
如果arr[pos1]+arr[pos2]<=arr[pos3]，那么pos2左边的元素加上arr[pos1]一定小于等于arr[pos3]，无法构成三角形，此时++pos1

直至pos1和pos2直至相撞，再–pos3，重复以上操作直至pos3<2

class Solution {
public:
    int triangleNumber(vector<int>& nums) 
    {
        int count=0;
        sort(nums.begin(),nums.end());
        int max_side=nums.size()-1;
        for(;max_side>1;--max_side)
        {
            int side1=0;
            int side2=max_side-1;
            while(side1<side2)
            {
                if(nums[side1]+nums[side2]>nums[max_side])
                {
                    count+=side2-side1;
                    --side2;
                }
                else
                {
                    ++side1;
                }
            }
        }

        return count;
    }
};

和为目标值的两个数

对数组排序使数据单调，left=0，right指向数组末尾，
如果price[left]+price[right]>target，那么left右边的元素加上price[right]也一定大于target，故此时只要–right即可
如果price[left]+price[right]<target，那么right左边的元素加上price[left]也一定小于target，故此时只要++left即可

class Solution {
public:
    vector<int> twoSum(vector<int>& price, int target) 
    {
        int left=0;
        int right=price.size()-1;
        vector<int> ret;
        while(left<right)
        {
            int sum=price[left]+price[right];
            if(sum==target)
            {
                ret.push_back(price[left]);
                ret.push_back(price[right]);
                break;
            }
            else if(sum<target)
            {
                ++left;
            }
            else
            {
                --right;
            }
        }

        return ret;
    }
};

三数之和

对数组排序，接着定一移二，对于pos1和pos2的移动参照前一题

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums)
    {
       vector<vector<int>> ret;
       sort(nums.begin(),nums.end());
       int pos3=nums.size()-1;
       while(pos3>1)
        {
            int pos1=0;
            int pos2=pos3-1;
            vector<int> tmp;
            while(pos1<pos2)
            {
                int sum=nums[pos1]+nums[pos2]+nums[pos3];
                if(0==sum)
                {
                    tmp.push_back(nums[pos1]);
                    tmp.push_back(nums[pos2]);
                    tmp.push_back(nums[pos3]);
                    ret.push_back(tmp);
                    tmp.clear();
                    ++pos1;
                    while(pos1<pos2&&nums[pos1-1]==nums[pos1])
                    {
                        ++pos1;
                    }
                }
                else if(sum>0)
                {
                    --pos2;
                }
                else
                {
                    ++pos1;
                }
            }
            --pos3;
            while(pos3>1&&nums[pos3]==nums[pos3+1])
            {
                --pos3;
            }
        }

        return ret;
    }
};

四数之和

对数组排序，接着定二移二，对于pos1和pos2的移动参照前2题

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) 
    {
        sort(nums.begin(),nums.end());
        int pos4=nums.size()-1;
        vector<vector<int>> vv;
        while(pos4>2)
        {
            int pos3=pos4-1;
            while(pos3>1)
            {
                int pos2=pos3-1;
                int pos1=0;
                while(pos1<pos2)
                {
                    if(pos1<pos2)
                    {
                        //溢出处理
                        int sum=nums[pos1];
                        vector<int> tmp={nums[pos2],nums[pos3],nums[pos4]};
                        int i=0;
                        int flag=0;
                        while(i<3)
                        {
                            if(sum>=0)
                            {
                                if(tmp[i]>0&&INT_MAX-sum<tmp[i])
                                {
                                    --pos2;
                                    flag=1;
                                    break;
                                }
                                sum+=tmp[i];
                            }
                            else
                            {
                                if(tmp[i]<0&&INT_MIN-sum>tmp[i])
                                {
                                    ++pos1;
                                    flag=1;
                                    break;
                                }
                                sum+=tmp[i];
                            }
                            ++i;
                        }
                        if(flag)
                        {
                            continue;
                        }

                        if(sum==target)
                        {
                            vector<int> v={nums[pos1],nums[pos2],nums[pos3],nums[pos4]};
                            vv.push_back(v);
                            --pos2;
                            while(pos2>0&&nums[pos2]==nums[pos2+1])
                            {
                                --pos2;
                            }
                        }
                        else if(sum>target)
                        {
                            --pos2;
                        }
                        else
                        {
                            ++pos1;
                        }
                    }
                }
                --pos3;
                while(pos3>0&&nums[pos3]==nums[pos3+1])
                {
                    --pos3;
                }
            }
            --pos4;
            while(pos4>=0&&nums[pos4]==nums[pos4+1])
            {
                --pos4;
            }
        }

        return vv;
    }
};