算法专题一：双指针

一：移动零

移动零

1.GIF题目解析：

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

二：复写零

复写零

2.GIF题目解析：

情况一：

情况二

class Solution {
public:
    void duplicateZeros(vector<int>& arr) {

        int cur = 0;
        int des = -1;
        int n = arr.size();

        //1.找到cur和des位置：

        while (cur<n)
        {
            if (arr[cur] != 0)
            {
                des++;
            }
            else if (arr[cur] == 0)
            {
                des += 2;
            }
            if (des >= n - 1)
            {
                break;
            }
            cur++;
        }


        //2.判断特殊情况：
        if (des == n)
        {
            arr[n-1] = 0;
            cur--;
            des-=2;
        }

        //3.进行复写操作：

        while (cur >= 0)
        {
            if (arr[cur] != 0)
            {
                arr[des--] = arr[cur];
            }
            else
            {
                arr[des--] = 0;
                arr[des--] = 0;
            }
            cur--;
        }
    }
};

三：快乐数

快乐数

3.GIF题目解析：

class Solution {
public:
    int sum_of_squares(int n)
    {
        int sum = 0;
        while(n!=0)
        {
            int tmp = n%10;
            sum += (tmp*tmp);
            n/=10;
        }
        return sum;
    }

    bool isHappy(int n) {
        int slow = n;
        int falst = sum_of_squares(n);

        while(slow!=falst)
        {
            slow = sum_of_squares(slow);
            falst = sum_of_squares(sum_of_squares(falst));
        }

        return slow==1;
    }
};

四：装水最多容器：

4.GIF题目解析：

class Solution {
public:
    int maxArea(vector<int>& height) {
        int front = 0;
        int last = height.size()-1;

        int capacity = 0;
        while(front<=last)
        {
            int cap = (min(height[last] , height[front]))*(last-front);

            if(cap>=capacity)
            {
                capacity = cap;
            }

            if(height[front]>=height[last])
            {
                last--;
            }
            else if(height[front]<height[last])
            {
                front++;
            }
        }

        return capacity;
    }
};

五：有效三角形的个数：

有效三角形的个数

思路一：暴力解法：
1.满足三角形的条件是任意两边之和大于第三边：
2.题目不允许同一个位置的元素重复出现：
3.因为只需要拿出三个数所以循环遍历三次：
4.三角形条件的判断需要判断三次：
5.时间复杂度就是O(3*N^3)

思路二：排序+双指针

5.GIF题目解析：

class Solution {
public:
    int triangleNumber(vector<int>& nums) {

        //1.排序
        sort(nums.begin(),nums.end());

        //2.固定最大的数：
        int count =0;

        for(int i=nums.size()-1;i>=2;i--)
        {
            int left = 0;
            int right = i-1;

            while(left<right)
            {
                int sum = nums[left]+nums[right];

                if(sum > nums[i])
                {
                    count+=(right-left);
                    right--;
                }
                else if(sum <= nums[i])
                {
                    left++;
                }
            }
        }
        return count;
    }
};

六：查找总价格为目标价格的两个商品：

查找总价格为目标价格的两个商品

思路一:暴力解法：
1.双for循环可以重复遇到满足情况的值就返回：
2.双for的i和j price[i]+price[j] == target

思路二：排序+双指针

6.GIF题目解析：

class Solution {
public:
    vector<int> twoSum(vector<int>& price, int target) {
        //1.排序：
        sort(price.begin(),price.end());
        //2.确定指针位置和三种情况：
        int left=0;
        int right = price.size()-1;

        while(left<right)
        {
            int sum = price[left]+price[right];

            if(sum > target)
            {
                right--;
            }
            else if(sum<target)
            {
                left++;
            }
            else 
            {
                return {price[left],price[right]};
            }
        }
        return {-1,-1};
    }
};

七：三数之和：

三数之和

class Solution {
    bool pwd(vector<int>& v1,vector<vector<int>>& vv)
    {
        int flag = vv.size();

        for(int i=0;i<vv.size();i++)
        {
            vector<int> v2=vv[i];

            for(int i=0;i<3;i++)
            {
                if(v1[i]!=v2[i])
                {
                    flag--;
                    break;
                }
            }
        }

        if(flag == 0)
        {
            return false;
        }
        else 
        {
            return true;
        }
    }
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> vv;
        for(int i=0;i<nums.size();i++)
        {
            for(int j=i+1;j<nums.size();j++)
            {
                for(int k=j+1;k<nums.size();k++)
                {
                    int sum = nums[i]+nums[j]+nums[k];
                    vector<int> tmp ={nums[i] , nums[j] ,nums[k]};
                    //1.排序：
                    sort(tmp.begin(),tmp.end());

                    if(sum==0)
                    {
                        //2.判断是否重复：
                        if(vv.size()==0)
                        {
                            vv.push_back(tmp);
                            continue;
                        }
                        else if(!pwd(tmp,vv))
                        {
                            vv.push_back(tmp);
                        }
                    }
                    
                }
            }
        }
        return vv;
    }
};

7.GIF题目解析：

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {

        vector<vector<int>> vv;
        //1.排序：
        sort(nums.begin(), nums.end());
        //2.遍历固定一个
        if ((nums.size() == 3) && (nums[0] + nums[1] + nums[2] == 0))
        {
            vv.push_back(nums);
            return vv;
        }

        for (int i = 0; i <nums.size();)
        {
            int des = -(nums[i]);

            if(nums[i] > 0)
                break;

            int left = i+1;
            int right = nums.size()-1;

                while (left < right)
                {
                    int sum = nums[left] + nums[right];

                    if (sum > des && right >= 0)
                    {
                        right--;
                    }
                    else if (sum < des && left < nums.size())
                    {
                        left++;
                    }
                    else
                    {
                        vector<int> tmp = { nums[left],nums[right],nums[i] };
                        vv.push_back(tmp);

                        left++;
                        right--;

                        while(left<right && nums[left]==nums[left-1])
                            left++;
                        while(left<right && nums[right]==nums[right+1])
                            right--;
                    }
               }

                i++;
                while(i<nums.size() && nums[i]==nums[i-1])
                i++;
            }

            return vv;
        }
};

八：四数之和：

四数之和

8.GIF题目解析：

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {

        //1.排序：
        sort(nums.begin(),nums.end());

        //2.记录数据个数：
        int n=nums.size();
        vector<vector<int>> vv;
        //3.开始遍历：

        //情况一：
        
        //特殊优化！
        if(nums[0]>target && nums[0]>0)
            return vv;

        //情况二：
        for(int i=0;i<n;)
        {
            for(int j=i+1;j<n;)
            {
                int left=j+1;
                int right = n-1;

                long long   sum_1 = ((long long)target - 
                (long long)(nums[i] + nums[j]));

                while(left<right)
                {
                    long long  sum_2 = nums[left]+nums[right];

                    if(sum_2 > sum_1)
                    {
                        right--;
                    }
                    else if(sum_2 < sum_1)
                    {
                        left++;
                    }
                    else
                    {
                        vector<int> tmp={nums[i],nums[j],nums[left],nums[right]};
                        vv.push_back(tmp);
                        right--;
                        left++;

                        while(left<right && nums[right]==nums[right+1])
                            right--;
                        while(left<right && nums[left]==nums[left-1])
                            left++;
                    }

                }
                j++;
                while(j<n && nums[j]==nums[j-1])
                    j++;
            }

            i++;
            while(i<n && nums[i] == nums[i-1])
                i++;
        }
        return vv;
    }
};