目录

1.移动零

2.复写零

3.快乐数

4.盛水最多的容器

5.有效三角形的个数

6.和为s的两个数

7.三数之和

8.四数之和

总结：

---

1.移动零

将数组中所有的0移动到数组末尾，并且不能开辟新数组。

算法原理：

数组划分，把一整个数组（直线表示）用一个分割线，划分成2部分，分别是左边的非零元素，还有右边的0

一般用双指针来解决数组划分问题，在数组问题中利用数组下标充当指针

---

cur：从左往右扫描，遍历数组

dest：已处理的区间内，非零元素的最后一个位置

三个区间：

[0,dest]:存放非零元素

[dest+1,cur-1]:存放0

[cur,n-1]:待处理区间

---

初始化时，dest放数组前面，cur放数组首元素。

cur遇到0直接往后一位，遇到非零元素让dest往后一位，同时交换dest和cur的元素，非边界情况下交换的都是0与非零元素（也不算特别边界其实）

---

边界情况下，例如[1,0,0]，dest和cur同时指向1，1和1交换位置不动，依旧能满足操作

例如[0]，cur会直接遍历完整个数组，依旧满足操作

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

2.复写零

请不要在超过该数组长度的位置写入元素。请对输入的数组就地进行上述修改，不要从函数返回任何东西。

把数组中出现的每一个0都复写一遍

思路A：

不管题目的要求，开辟一个新数组，把旧数组遍历一遍，如果是非零元素直接放到新数组中，如果是0就一次放2个0到新数组中。

---

思路B：

如果cur和dest都从同一个数组的开头往后移动，那么肯定有元素会被覆盖掉。

那么我们大可逆向思维，从后往前移动。

第一步：dest指向最后一个元素，cur指向最后一个需要复写的数

第二步：如果非零元素，就直接cur指向元素覆盖掉dest指向元素，然后统一向前1位；如果为0，就一次覆盖两个dest的元素（紧邻的2个），然后cur向前1位

第三步：当cur或dest出了数组，结束操作

现在的难点就在于，怎么让cur指向最后一个需要复写的数呢？

那我们就模仿第二步，搞出一个没有复写操作的逆操作，依旧可以完成这个目标

cur遇到非零元素，dest往后1步，cur也往后1步；cur遇到0，dest往后2步，cur往后1步

---

边界情况：

当0出现在了数组倒数第二个位置，然后dest +=2 后出现越界了怎么办？

直接让n-1下标的元素覆盖为0，然后dest -=2

class Solution {
public:
    void duplicateZeros(vector<int>& arr) {
        int cur,dest;
        
        //1.找数
        for(cur=0,dest=-1;cur<arr.size();cur++){
            if(arr[cur]) dest++;
            else dest+=2;
            if(dest >= arr.size()-1 ) break;
        }

        //2.处理边界情况
        if(dest == arr.size())
        {
            arr[arr.size()-1] = 0;
            cur--;
            dest-=2;
        }

        //3.从后向前完成复写操作
        while(cur >= 0)
        {
            if(arr[cur]) arr[dest--]=arr[cur--];
            else
            {
                arr[dest--] = 0;
                arr[dest--] = 0;
                cur--;
            }
        }
    }
};

3.快乐数

示例一：19中的 1^2 + 9^2 = 82，不断重复同一操作，最后就得到了 1^2 + 0 + 0 = 1（1不断循环成为1），这种就是快乐数

示例二：不断重复同一操作后，不难发现会回到4这个数字，然后又开始新一轮的循环，但是永远都不会到 1 的结果，因此就不是快乐数

通过两个示例，我们可以抽象组合成一个模型。一个最后会进行1的不断循环，一个最后会进入非1数字的循环圈。因此无论是否为快乐数，最后都能够进入一个循环圈

这就能和判断链表环结合起来，即判断环中的数是否全为1

在判断链表是否有环的题目中，我们使用到了快慢指针，因此该题我们依旧可以使用快慢双指针的办法

---

本题在题干中声明：某数可能变为 1，也可能是无限循环但始终变不到 1。所以是必然有环的，就不需要考虑不存在环的情况了

但如果没有这个声明，我们依旧可以通过抽屉原理判断出必然成环

整型最大值2^31 - 1 = 2,147,483,647 ≈ 2.1 * 10^9

999999999 = 9.9 * 10^8，最后通过快乐数的那个加法操作算出来是 9^3 =729

1999999999 最后通过快乐数的加法操作算出来是 730 

因此无论n怎么变，最后的值算出来的范围都在[1,730]

根据抽屉原理（一个班级13个人，一定有2人生日在同一个月），至多进行731次快乐数的加法操作就一定能成环

---

算法原理：

1.定义快慢指针

2.慢指针每次向后移动1步，快指针每次向后移动2步

3.因为一定有环，所以快慢指针一定会相遇，判断相遇时候的值即可

---

我们可以把数字本身看作指针。

以示例1为例，slow = 2 -> slow = 4；fast = 2 -> fast = 16

class Solution {
public:
    int my_pow(int n)//返回n这个数每一位上的平方和
    {
        int sum=0;
        while(n)
        {
            int temp = n%10;
            sum += temp*temp;
            n/=10;
        }
        return sum;
    }
    bool isHappy(int n) {
        int slow = n, fast = my_pow(n);
        while(slow != fast)
        {
            slow = my_pow(slow);
            fast = my_pow(my_pow(fast));
        }
        return slow == 1;
    }
};

4.盛水最多的容器

每两条线相距为1，每条线的高度在数组中给出，找出两条线，要求所围绕的面积最大

思路A：

暴力解法就是把所有情况都算一遍（1和8结合、1和6结合、……8和6结合、8和2结合、……），把最大值找出来即可。过于暴力，leetcode不会通过的。

时间复杂度：n^2

---

思路B：

搞一个left，指向数组首元素；搞一个right，指向数组末元素。

当left与right不断向内夹逼的时候，宽度必然是不断减小的。

---

3种情况：

1.高度和宽度都降低 --> 体积降低

2.高度不变，宽度降低 --> 体积降低

3.高度变高，宽度降低 --> 体积可能升高也可能降低

例如[6,2,5,4]当中的4，与5、2、6相结合的时候高度恒为4，但宽度越来越大，所以4与6结合是最优的。可如果5与6结合，高度就变大了，体积就有更大的可能。因此我们可以提取出4与6结合的这种情况（4的最大情况），然后将right往左移动一位，试试5与6的结合（5的最大情况）。可如果是[6,2,3,4]的这种情况，right往左移动一位以后，高度和宽度都降低了，此时判断不判断没有影响了。

简而言之，就是遇到情况1、2都无关紧要，遇到情况3就判断大小（代码对3种情况都会进行判断，这样不会导致代码的冗余）

时间复杂度：n

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

5.有效三角形的个数

返回数组中可以形成三角形的三元组个数（不同位置的2算两个2）

形成三角形的条件：较小的2个数相加，大于较大的那个数

由此，优化：对数组进行排序，[4,2,4]三元组和[2,4,4]三元组对结果没有影响

思路A：

暴力枚举，搞出所有情况进行判断（伪代码的写法如上图）

时间复杂度：n^3

---

思路B：

从数组的末尾开始，固定下来一个最大的数，利用排序完的数组具有单调性来优化
情况1：left和right指向的a+b > c（指定数），那么left和right之间的所有数都满足 a + b > c

情况2：left和right指向的a+b <= c

遇到情况1，统计right - left 个三元组，都满足有效三角形。统计完之后，right所指向的元素已经所有情况都被考虑到了，因此可以去除，通过right -- 的方式来去除

遇到情况2，因为小的数过小，right减小之后，小的数和right指向的数也不会比c大。因此可以通过数组单调性直接把那个小的数给去除，通过left++的方式来去除，然后不断判断直到符合情况1

---

最后固定下数组中倒数第二大的数，重复上述操作……

时间复杂度：n^2

  

class Solution {
public:
    int triangleNumber(vector<int>& nums) {
        sort(nums.begin(),nums.end());

        int n = nums.size(),ret = 0;
        int left,right;
        for(int num = n-1;num >= 2;num--)
        {
            int left = 0,right = num-1;
            while(left < right)
            {
                if(nums[left]+nums[right]>nums[num])
                {
                    ret += right-left;
                    right--;
                }
                else left++;
            }
        }
        return ret;
    }
};

6.和为s的两个数

数组中找出2个数，相加等于指定值。

利用排序完的数组具有单调性+左右指针向内夹逼来解决

class Solution {
public:
    vector<int> FindNumbersWithSum(vector<int> array,int sum) {
        int left=0,right=array.size()-1;
        while(left<right)
        {
            if(array[left]+array[right]>sum) right--;
            else if(array[left]+array[right]<sum) left++;
            else return {array[left],array[right]};
        }
        return {};//一定要有个数组类型返回值
    }
};

7.三数之和

数组中三个不同位置的数相加为0，构成无序三元组，不同顺序但数字相同的三元组挑一个返回即可，不需要全部返回。怎么都不可能形成所需的三元组时，返回空数组

通过排序可以简化整道题目。

证明：以示例1为例，排序之后就会有[-4,-1,-1,0,1,2]，即使出现数字相同的两个三元组，顺序也是必然相同的，这种情况下对我们“舍去其中一个”的操作非常有利。

思路A：

排序 + 暴力枚举 + 哈希表（unordered_set）

时间复杂度：n^3

---

思路B：

固定数（有效三角形个数）+ 左右指针向内夹逼 + 排序 + 排序完的数组具有单调性

时间复杂度：n^2

---

例如下图所给的例子，固定了-4以后，右边那个区间的数组就可以转换到和为4的两个数字问题，但要转换成不停下来的和为s的两个数字问题

并且，找到一种结果后，left和right指针要跳过重复元素；当使用完1次某个固定数以后，不同位置的同一固定数不能再用了，也要跳过。这样做可以有效去重

当也要考虑到下图出现的特殊情况，这时left或者right可能会越界访问

最后，当固定数比0大时，那么后面的情况都可以直接排除了，因为三个正数相加不可能为0；同时，如果数组中全是正数或全是正数的情况下，可以直接返回空数组了

  

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> ret;
        int n = nums.size();
        sort(nums.begin(),nums.end());
        if(nums[0] > 0 || nums[n-1] < 0) return {};
        for(int i = 0;i < n-2;)
        {
            if(nums[i] > 0) break;
            int left = i+1,right = n-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({nums[i],nums[left],nums[right]});
                    left++,right--;
                    while(nums[left] == nums[left-1] && left < n - 1) left++;
                    while(nums[left] == nums[left-1] && right > i + 1) right--;
                }
            }
            i++;
            while(i < n - 2 && nums[i] == nums[i-1]) i++;
        }
        return ret;
    }
};

8.四数之和

该题就是基于“三数之和”又添加了一个数

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        vector<vector<int>> ret;
        int n=nums.size();
        long int sum=0;
        sort(nums.begin(),nums.end());
        for(int a=0;a<n;)
        {
            for(int b=a+1;b<n;)
            {
                int left=b+1,right=n-1;
                long long flag=(long long)target-nums[a]-nums[b];
                while(left<right)
            {
                sum=nums[left]+nums[right];
                if(sum>flag)right--;
                else if(sum<flag)left++;
                else
                {
                    ret.push_back({nums[left],nums[right],nums[a],nums[b]});
                    right--;
                    left++;
                    while(left<right&&nums[right]==nums[right+1])right--;
                    while(left<right&&nums[left]==nums[left-1])left++;
                }
            }
            b++;
            while(b<n&&nums[b]==nums[b-1])b++;
            }
            a++;
            while(a<n&&nums[a]==nums[a-1])a++;
        }
        return ret;
    }
};

总结：

画图、数组划分（分割线）、固定数思维、逆向思维、（链表）环判断思想、快慢指针、抽屉原理、函数封装、左右指针向内夹逼、 单调性、排序

双指针只是一种思想，可以把数组下标视为指针（1、2题），甚至可以把某一个数字作为指针（3题）

C++特殊用法：在函数中，return {X,Y} 就相当于返回了一个有2个元素的数组，return { } 就相当于返回了一个空数组，return{X,Y,Z}就相当于返回了一个有3个元素的数组