【LeetCode18】【双指针】每日一题day32

题面：
给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组。

这道题我一看，和组合总和差不多嘛，十分钟就写了个回溯，结果一堆bugTvT 虽然它最后还是超时了，但是有一些写回溯的心得我要写一下

class Solution {
public:
    void recall(vector<int> nums, vector<int> &res,
set<vector<int>> &st, int target, int cur)
    {
        if (target == 0 && res.size() == 4)
        {
            st.insert(res);
            return;
        }
        else if (res.size() == 4)
        {
            return;
        }
        // 判断是否遍历完整个数组，要在把可能的答案丢进ans之后
        if (cur == nums.size())
        {
            return;
        }

        res.push_back(nums[cur]);
        recall(nums, res, st, target - nums[cur], cur + 1);
        res.pop_back();
        recall(nums, res, st, target, cur + 1);
    }
    
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        int size = nums.size();
        vector<vector<int>> ans;
        if (size < 4) return ans;
        sort(nums.begin(), nums.end());
        vector<int> res;
        set<vector<int>> st;
        recall(nums, res, st, target, 0);
        ans.assign(st.begin(), st.end());
        return ans;
    }
};

本来想用unordered_map，但是它是用hashtable实现的，而vector<int>没有哈希值，我还不太会自定义，就换成了消耗大一些的set
一开始先排序，再用set对答案去重是我做组合总和时候的惯用套路了_(:з」∠)_ 但是我不知道这道题里面的超时是不是我回溯写的不好的原因

顺便学了一下vector用unique函数去重，但是这道题不能一开始直接给nums去重，因为它4个数里面可能会有重复的。

vector<int> ver;
sort(ver.begin(), ver.end());
vector<int>::iterator iter = unique(ver.begin(), ver.end());
ver.erase(iter,ver.end());
for(int *t = ver.begin(); t != ver.end(); t++)
{
	printf("%d ",*t);
}

双指针听起来好像很高级，其实就是遍历的时候从两头同时开始，排完序之后一头大一头小，对于得到某个特定值的问题就可以迅速知道大了还是小了要怎么调整。

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        sort(nums.begin(), nums.end());
        int size = nums.size();
        vector<vector<int>> ans;
        vector<int> res;
        for (int i = 0; i < size - 3; i++)
        {
            if (i > 0 && nums[i] == nums[i - 1]) continue;
            int rem = target;
            res.push_back(nums[i]);
            rem -= nums[i];
            for (int j = i + 1; j < size - 2; j++)
            {
                if (j > i + 1 && nums[j] == nums[j - 1]) continue;
                res.push_back(nums[j]);
                int tmp1 = rem - nums[j];
                int l = j + 1, r = size - 1;
                while (l < r)
                {
                    int tmp2 = tmp1 - nums[l] - nums[r];
                    if (tmp2 == 0)
                    {
                        res.push_back(nums[l]);
                        res.push_back(nums[r]);
                        ans.push_back(res);
                        res.pop_back();
                        res.pop_back();
                        l++, r--;
                        while (l < r && nums[l] == nums[l - 1]) 
                        {
                            l++;
                        }
                        while (l < r && nums[r] == nums[r + 1] && r < size - 1)
                        {
                            r--;
                        }
                    }
                    else if (tmp2 > 0)
                    {
                        l++;
                    }
                    else if (tmp2 < 0)
                    {
                        r--;
                    }
                    
                }
                res.pop_back();
            }
            res.pop_back();
        }
        return ans;
    }
};

为了避免得到重复答案，我们要在遍历i、j的时候跳过相同的数字，并且在得到某一答案后让指针跳过相同数字。
我用了rem、tmp1和tmp2来存放中间值，因为每一层里面它们是不能随之改变的。

这篇题解写了思考路线，很清楚，怎么能想到一个问题的解法是我想要学习并且在自己的题解里面写出来的。
还有这一段写的好棒呀，我就是每次打补丁把代码搞臭的人hhh

我们刚刚的解法，会在 [0,0,0,0] 这个情况下败下阵来，此时有两个解决方案，第一种就是直接堵上漏洞，针对有问题的测试数据在代码中加补丁。如果运气好的话，可能下一次提交就会 AC 了。但是这种方法在竞赛中是不可取的，因为一次 WA 会有罚时。在工作中我们可能顺手就打补丁修了问题，然后等到测试报出其他问题再去修。如果测试恰好没有发现任何问题，这段代码就可以上线了。但是这样带来的问题，一是并没有在逻辑层面消除某一类特殊数据可能带来的问题，二是代码会很丑陋，变得难以维护。

所以更好的做法是：从这个不通过的数据提取特征，添加对应特征数据的处理逻辑，一次修复一类的错误，并且尽量保持代码的流畅。