基于leetcode的算法训练：Day2

_{在考虑要不要改成打卡……算了，还是喜欢佛系一点🧐}

1. 数组中和为0的三个数

题目要求:给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请

你返回所有和为 0 且不重复的三元组。

题目链接：剑指 Offer II 007. 数组中和为 0 的三个数 - 力扣（LeetCode）

**题目难度：**✨✨

暴力会超时：

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        //三个数字加起来为0
        set<vector<int> >ans;
        vector<int>temp(3);
        int len=nums.size();
        sort(nums.begin(),nums.end());
        for(int i=0;i<len-2;i++){
            if(nums[i]>0){
                break;
            }
            for(int j=i+1;j<len-1;j++){
                if(nums[i]+nums[j]>0){
                    break;
                }
                for(int k=j+1;k<len;k++){
                    if(nums[i]+nums[j]+nums[k]>0){
                        break;
                    }
                    if(nums[i]+nums[j]+nums[k]==0){
                        temp[0]=nums[i];
                        temp[1]=nums[j];
                        temp[2]=nums[k];
                        ans.insert(temp);
                    }
                }
            }
        }
        vector<vector<int> >res;
        for(set<vector<int> >::iterator it=ans.begin();it!=ans.end();it++){
            res.push_back(*it);
        }
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

参考官方题解：

如何才能有效暴力捏？

因为题目中提到了对于输出顺序 不 care，所以先排序，避免出现(a,b,c)(a,c,b)等重复的问题

接着三重遍历暴力可以通过近乎80%的样例，说明主要原因在于在此框架下的剪枝

对于第一重循环，要避免两次遍历的num[i]是同一个值

对于第二重循环，也要避免在num[i]相同情况下，两次遍历的num[j]是同一个值

当num[i]和num[j]确定后，其实num[k]的值也确定了，唯一需要确定的是k的位置是否大于j，符合条件的话记录这一次答案，不符合条件说明num[i]已经到头了，再遍历j，num[j]和num[k]都变大不可能再有符合条件的值，故而跳出j层循环
所以其实可以看做是一个逻辑上的二重循环

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int> >ans;
        sort(nums.begin(),nums.end());
        int len=nums.size();
        int i,j,k;
        for(i=0;i<len-2;i++){
            if(i&&nums[i]==nums[i-1]){
                //避免第一个重复
                continue;
            }
            k=len-1;
            for(j=i+1;j<len-1;j++){
                if(j>i+1&&nums[j]==nums[j-1]){
                    //避免第二个重复
                    continue;
                }
                while(k>j&&nums[j]+nums[k]+nums[i]>0){
                    k--;
                }
                //很关键的及时跳出循环
                if(k==j){
                    break;
                }
                if(nums[j]+nums[k]+nums[i]==0){
                    ans.push_back({nums[i],nums[j],nums[k]});
                }
            }
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33