数组

1.两数之和 简单

class Solution {
    public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int,int> memo;
        for(int i=0;i<nums.size();i++){
            if(memo.count(nums[i])==0){
                memo.insert(make_pair(target-nums[i],i));
            }else{
                return {memo[nums[i]],i};
            }
        }
        return {}; 
    }
};

用哈希表做备忘
11.盛最多水的容器 中等

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

• 双指针
• 用 left 和 right 两个指针从两端向中心收缩，一边收缩一边计算 [left, right] 之间的矩形面积，取最大的面积值即是答案。
• key：指针收缩向更矮的方向，因为短的才是决定容量的

15.三数之和

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> res;
        if(nums.size()<3){
            return res;
            //真是坏！
        }
        sort(nums.begin(),nums.end());
        for(int i=0;i<nums.size()-2;i++){
            if(nums[i]>0){
                return res;
            }
            if(i>0&&nums[i]==nums[i-1]){
                continue;
                //注意点一，去重
            }
            int L=i+1;
            int R=nums.size()-1;
            while(L<R){
                if(nums[i]+nums[L]+nums[R]==0){
                    res.push_back({nums[i],nums[L],nums[R]});
                    while(R>L&&nums[L]==nums[L+1]) L++;
                    while(R>L&&nums[R]==nums[R-1]) R--;
                    L++;
                    R--;
                }else if(nums[i]+nums[L]+nums[R]<0){
                    while(L<R&&nums[L+1]==nums[L]) L++;
                    L++;
                }else{
                     while(L<R&&nums[R-1]==nums[R]) R--;
                     R--;
                }
            }
        }
        return res;
    }
};

16.最接近的三数之和

class Solution {
public:
    int threeSumClosest(vector<int>& nums, int target) {
        int closest=nums[0]+nums[1]+nums[2];
        sort(nums.begin(),nums.end());
        for(int i=0;i<nums.size()-2;i++){
            if(i>0&&nums[i]==nums[i-1]){
                continue;
            }
            int L=i+1;
            int R=nums.size()-1;
            while(L<R){
                int curDif=abs(nums[i]+nums[R]+nums[L]-target);
                int prevDif=abs(closest-target);
                closest=prevDif>curDif?(nums[i]+nums[R]+nums[L]):closest;
                if(nums[i]+nums[R]+nums[L]>target){
                    while(L<R&&nums[R-1]==nums[R]) R--;
                    R--;
                }else{
                    while(L<R&&nums[L+1]==nums[L]) L++;
                    L++;
                }
            }
        }
        return closest;
    }
};

这种是考虑到不会出现正好等于target的情况的，不然的话和之前三数之和一样
考虑了=target的情况？因为else的情况包含了，而且可能会重复，但是因为只要求返回和，而不是组合所以没差。
18.四数之和

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        vector<vector<int>> res;
        if(nums.size()<4) return res;
        sort(nums.begin(),nums.end());
        for(int i=0;i<nums.size();i++){
            if(i>0&&nums[i]==nums[i-1]) continue;//去重
            for(int j=i+1;j<nums.size();j++){
                if(j>i+1&&nums[j-1]==nums[j]) continue;//去重
                int L=j+1;
                int R=nums.size()-1;
                while(L<R){
                    if(nums[i] + nums[j]  > target - (nums[L] + nums[R])){
                        //overflow！
                        while(L<R&&nums[R]==nums[R-1]) R--;
                        R--;
                    }else if(nums[i] + nums[j]  < target - (nums[L] + nums[R])){
                        //overflow！
                        while(L<R&&nums[L]==nums[L+1]) L++;
                        L++;
                    }else{
                        res.push_back({nums[i],nums[j],nums[L],nums[R]});
                        while(L<R&&nums[L]==nums[L+1]) L++;
                        while(L<R&&nums[R]==nums[R-1]) R--;
                        L++;
                        R--;
                    }
                }
            }
        }
        return res;
    }
};

:::tips 关于n数之和问题；

• 首先要对数组做有序化
• 有序化之后才能使用双指针
• 对于n数之和不过是多次嵌套
• 问题的难点在于如何去重以及在哪里去重 ::: :::info 双指针的问题：

1. 什么时候收缩？
2. 往哪里收缩？
3. 要不要去重，如何去重
4. 如果不让重拍如何去重 :::

26.删除有序数组中的重复项

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        if(nums.empty()){
            return 0;
        }
        int fast=0;
        int slow=0;
        while(fast<nums.size()){
            if(nums[fast]!=nums[slow]){
                slow++;
                nums[slow]=nums[fast];//赋值而不是交换
            }
            fast++;
        }
        return slow+1;
    }
};

本质是让快指针去探路，找到不同的值，然后慢指针维护当前数组都是不重复的。

27.移除元素

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int fast=0;
        int slow=0;
        while(fast<nums.size()){
            if(nums[fast]!=val){
                nums[slow]=nums[fast];
                slow++;
            }
            fast++;
        }
        return slow;
    }
};

快指针去探路，找到不是val的值，和上一个一样的想法。
75.颜色分类
经典快排序

class Solution {
public:
    void sortColors(vector<int>& nums) {
        int red=-1;
        int blue=nums.size();
        int l=0;
        while(l<blue){
            if(nums[l]==0){
                swap(nums[++red],nums[l]);
                l++;//why?
            }else if(nums[l]==2){
                swap(nums[--blue],nums[l]);
            }else{
                l++;
            }
        }  
    }
};

31. 下一个排列
Medium

class Solution {
    public:
    void nextPermutation(vector<int>& nums) {
        int index=-1;
        for(int i=nums.size()-1;i>0;i--){
            if(nums[i]>nums[i-1]){
                index=i;
                break;
            }
        }
        if(index==-1){
            sort(nums.begin(),nums.end());
            return;
        }
        int nxtmin=index;
        for(int i=index;i<nums.size();i++){
            if(nums[i]>nums[index-1]){
                nxtmin=i;
            }else{
                break;
            }
        }
        swap(nums[index-1],nums[nxtmin]);
        reverse(nums.begin()+index,nums.end());
    }
};

33. 搜索旋转排序数组
Medium

class Solution {
public:
    int search(vector<int>& nums, int target) {
           int lo = 0, hi = nums.size() - 1;
        while (lo < hi) {
            int mid = (lo + hi) / 2;
            if ((nums[0] > target) ^ (nums[0] > nums[mid]) ^ (target > nums[mid]))
                lo = mid + 1;
            else
                hi = mid;
        }
        return lo == hi && nums[lo] == target ? lo : -1;
    }
};