优选算法[1]

目录

1.双指针；

2.滑动窗口；

3.二分查找；

4.前缀和；

1.双指针；

包括对撞指针和快慢指针(一般用来循环）；

题目类型：移动零，复写零，快乐数，盛水最多的容器，有效三角形的个数，三数之和，四数之和。

举个例子：

移动零：

首先考虑暴力方法：直接遇到0元素插入到数组结尾。

优选之后：使用两个指针 (记录下标，并非真正的指针）；cur和dest。

cur如果遇到0元素就++，非零元素就和dest进行交换，交换之后dest++；直到cur走到结尾。

代码编写：

class Solution 
{
public:
    void moveZeroes(vector<int>& nums) 
    {
       int cur=0,dest=-1;
       while(cur<nums.size())
       {
          if(nums[cur]==0)
          {
              cur++;
          }
          else
          {
              dest++;
              swap(nums[dest],nums[cur]);
              cur++;
          }
       }
    }
};

复写零：

如果指针此c前面开始复写会造成数据被覆盖的问题，那么采用从后面到前面的方法。

首先进行移动指针，cur遇到非零移动一步，dest移动一步，cur遇到零移动一步，dest移动两步。

还有特殊情况dest跳出边界了；就把 arr[dest-1]=0;dest-=2;cur-=1;

看cur的值是否为0，非零就将cur的值直接赋值给dest，是零就赋值两次给dest。直到cur遍历完。

代码编写：

class Solution 
{
public:
    void duplicateZeros(vector<int>& arr) 
    {
        int dest=-1;int cur=0;int n=arr.size();
        //将指针移动尾部
        while(cur<n)
        {
            if(arr[cur])
            {
                dest++;
            }
            else
            {
                dest+=2;
            }
            
            if(dest >= n-1) break;
            cur++;
        }
        
        //处理边界,可能跳出范围了
        if(dest == n)
        {
            arr[dest-1]=0;
            dest-=2;
            cur--;
        }
        
     
        while(cur >= 0)
        {
            if(arr[cur])
            {
                arr[dest--]=arr[cur--];    
            }
            else
            {
                arr[dest--]=0;
                arr[dest--]=0;
                cur--;
            }
        }
        
    }
};

三数之和：

采用双指针的方法，首先固定一个数，只要找到和这个数相反的数之和就可以找到其他两个数。

那么就在 [i+1,n-1]之间进行查找。如果其和大于 t 那么就要将右边指针移动后一步；如果其和小于 t 那么就要将左边指针移动前一步。找到也不能停止，看是否有其他选择。

那么这里就会涉及到两个去重的操作。首先是left和right区间的去重，和上一次一样的数就直接跳过即可。外面固定的数也是一样的去重操作。

上代码：

class Solution 
{
public:
    vector<vector<int>> threeSum(vector<int>& nums) 
    {
        int n=nums.size();
        vector<vector<int>> ret;
        
        //先进行排序
        sort(nums.begin(),nums.end());
        
        for(int i=0;i<n;)
        {
            
            int left=i+1;int right=n-1;int target=-nums[i];
            
            while(left < right)
            {
                int sum=nums[left]+nums[right];
                if(sum < target)
                {
                    left++;
                }
                else if(sum > target)
                {
                    right--;
                }
                else
                {
                   //如果找到那么就插入ret，并且往后面看看，找到不同的解，如果有重复元素就跳过。
                   ret.push_back({nums[i],nums[left],nums[right]});
                   right--;left++;
                   
                   //跳过步骤
                   while(left < right && nums[left]==nums[left-1]) left++;
                   
                   while(left <right &&nums[right]==nums[right+1])
                   right--;
                }
                
            }
            i++;
            //i也是看重复元素.这个很考验能力，到底写哪里很重要。
            while(i < n && nums[i]==nums[i-1]) i++;
        }
        return ret;
    }
};

2.滑动窗口；

题目类型：长度最小的子数组，无重复字符的最长子串，最大连续1的个数，将x减少到零的最小操作数，。题目就是找进入窗口，出窗口，更新数据。

长度最小的子数组：

left和right，sum+=right的值，并且与 t 比较，len记录长度，大于t的话出窗口，更新len=right-left+1;并且left++。

上代码：

class Solution 
{
public:
    int minSubArrayLen(int target, vector<int>& nums) 
    {
        //滑动窗口的题目就是1.进入窗口，2.出窗口，3.更新结果；
        //多看过程；
        int left=0,right=0;
        int len=INT_MAX;
        int sum=0;

       //while循环进不去；for循环简单。
        for(int left=0,right=0;right<nums.size();right++)
        {
            //不进窗口就right++并且sum+;
            sum+=nums[right];
            //进窗口就判断小于，不断修改len以及sum.直到出去窗口；
            //相当于两层循环。
            while(sum >= target)
            {
               len=min(len,right-left+1);
               sum-=nums[left++];
            }
        }
        return len==INT_MAX?0:len;
    }
};

3.二分查找；

定义left和right的指针。

分为朴素二分和复杂二分。

左右指针以及中间指针进行移动，来查找数据。

注意分析left,right,mid的取值。结束条件。

二分查找：

class Solution 
{
public:
    int search(vector<int>& nums, int target) 
    {
         int left =0,right=nums.size()-1;

         while(left <= right)
         {
            int mid=left+(right-left)/2;
            if(nums[mid] < target)
            {
                left=mid+1;
            }
            else if(nums[mid] > target)
            {
                right=mid-1;
            }
            else
            {
                return mid;
            }
         }
         return -1;
    }
};

 复杂二分：

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

        if(nums.size()==0) return {-1,-1};
        //找左端点；
        int begin=0;
        int left=0,right=nums.size()-1;
        while(left < right)//自己画图分析是否等于
        {
            int mid=left+(right-left)/2;//自己分析；
            if(nums[mid] < target)
            {
                left=mid+1;
            }
            else 
            {
                right=mid;
            }
        }
        //判断是否有结果
        if(nums[left] != target)
        {
            return {-1,-1};
        }
        else
        {
            begin=left;
        }
        

        //找右端点
        left=0,right=nums.size()-1;
        while(left < right)
        {
            int mid=left+(right-left+1)/2;//自己分析；
            if(nums[mid] <= target)
            {
                left=mid;
            }
            else
            {
                right=mid-1;
            }
        }
        return {begin,right};
    }
};

4.前缀和；

1.首先找规律，创建dp前缀和数组使用前缀和数组，完成要求。

#include <iostream>
using namespace std;
#include<vector>

int main() 
{
   // 1.读入数据
    int n,q;
    cin>>n>>q;
    vector<int> arr(n+1);

    for(int i=1;i<=n;i++) cin>>arr[i];

    //预处理出来前缀和数组；
    vector<long long> dp(n+1);
    for(int i=1;i<=n;i++) dp[i]=dp[i-1]+arr[i];

    //使用前缀和数组；
    int l = 0,r=0;
    while(q--)
    {
        cin>>l>>r;
        cout<<dp[r]-dp[l-1]<<endl;
    }

    return 0;
}