优选算法第一讲：双指针模块

1.移动零

链接: 移动零
下面是一个画图，其中，绿色部分标出的是重点：

代码实现：

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        //定义双指针
        for(int cur = 0, des = -1; cur < nums.size(); cur++)
        {
            //当cur指向的位置不为0时，才进行交换
            if(nums[cur])
            {
                swap(nums[cur], nums[++des]);//注意：先++des，再进行交换
            }
        }
    }
};

2.复写零

链接: 复写零

代码实现：

class Solution {
public:
    void duplicateZeros(vector<int>& arr) {
        //先找到src的位置
        int src = 0, des = -1, n = arr.size();
        while(src < n)
        {
            if(arr[src]) des++;
            else des+=2;
            if(des >= n-1) break;
            src++;
        }
        if(des == n)
        {
            //发生了越界时，修正des的位置
            arr[n-1] = 0;
            src--;
            des -= 2;
        }
        //从后向前复写
        while(des > 0)
        {
            if(arr[src])
                arr[des--] = arr[src--];
            else
            {
                arr[des--] = 0;
                arr[des--] = 0;
                src--;
            }
        }
    }
};

3.快乐数

链接: 快乐数

class Solution {
public:
    //按照题意求值
    int Value(int n)
    {
        //循环*10 %10，C语言中讲过
        int sum = 0;
        while(n)
        {
            int t = n % 10;
            sum += t*t;
            n = n /10;
        }
        return sum;
    }

    bool isHappy(int n) {
        int slow = n, fast = Value(n);
        while(slow != fast)
        {
            slow = Value(slow);
            fast = Value(Value(fast));
        }

        return slow == 1;
    }
};

4.盛最多水的容器

链接: 盛最多水的容器

代码实现：

class Solution {
public:
    int maxArea(vector<int>& height) {
        int left = 0, right = height.size()-1, ret = 0;
        while(left < right)
        {
            int H = min(height[left], height[right]);
            ret = max(ret, (right-left)*H);
            if(height[left] > height[right]) right--;
            else left++;
        }
        return ret;
    }
};

5.有效三角形的个数

链接: 有效三角形的个数

class Solution {
public:
    int triangleNumber(vector<int>& nums) {
        //1.先对数组进行排序
        sort(nums.begin(), nums.end());
        int sum = 0;
        for(int i = nums.size()-1; i>=2; i--)
        {
            //i为最大值的下标
            //使用双指针进行运算
            int left = 0, right = i-1;
            while(left < right)
            {
                if(nums[left] + nums[right] > nums[i])
                {
                    sum += right-left;
                    right--;
                }
                else left++;
            }
        }
        return sum;
    }
};

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

链接: 查找总价格为目标值的两个商品

class Solution {
public:
    vector<int> twoSum(vector<int>& price, int target) {
        //因为题目说明已经是升序了，所以我们不用再进行排序了
        //使用双指针算法
        int left = 0, right = price.size()-1;
        while(left < right)
        {
            if(price[left] + price[right] > target) right--;
            else if(price[left] + price[right] < target) left++;
            else return {price[left], price[right]};
        }
        return {0, 0};
    }
};

7.三数之和

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> ret;
        //1.先对数组进行排序
        sort(nums.begin(), nums.end());
        //对i的固定
        int i = 0;
        while(i <= nums.size()-3)
        {
            //双指针算法
            int left = i+1, right = nums.size()-1;
            while(left < right)
            {
                if(nums[left] + nums[right] > -nums[i]) right--;
                else if(nums[left] + nums[right] < -nums[i]) left++;
                else
                {
                    //当相等时，先插入数据
                    ret.push_back(vector<int>({nums[left], nums[right], nums[i]}));
                    //再处理去重问题
                    left++;
                    right--;
                    while(left < right && nums[left] == nums[left-1]) left++;
                    while(left < right && nums[right] == nums[right+1]) right--;
                }
            }
            //对i进行去重
            i++;
            while(i <= nums.size()-3 && nums[i] == nums[i-1]) i++;
        }
        return ret;
    }
};

8.四数之和

链接: 四数之和