【LeetCode.15】3Sum （C++）

阳光穿透心脏的1/2处 2022-04-25 03:10 175阅读 0赞

# 问题描述 #

> Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.  
> The solution set must not contain duplicate triplets.

必须明白，各个三元组不能重复，但三元组中是可以使用重复元素的。

# 示例 #

> Given array nums = \[-1, 0, 1, 2, -1, -4\],  
> A solution set is:  
> \[  
> \[-1, 0, 1\],  
> \[-1, -1, 2\]  
> \]

从示例来看，每个三元组是排序的，虽然题面上没有明说。下面的程序是能保证排序的。

# bi-directional 2Sum sweep #

思路来自于[Concise O(N^2) Java solution][Concise O_N_2_ Java solution]。  
标题意思即为双向的2Sum扫描，2Sum指[LeetCode第一题][LeetCode]的解题思路。

class Solution { 
    public:
        vector<vector<int>> threeSum(vector<int>& nums) { 
            sort(nums.begin(), nums.end());
            vector<vector<int>> res;
            for(int i=0;i<nums.size();i++){ 
                if( i==0 || (i > 0 & nums[i] != nums[i-1]) ){ 
                    int low = i+1; int high = nums.size()-1;
                    //high变量不用担心，最后肯定会转成有符号数
                    int sum = - nums[i];
                    while(low < high){ 
                        if( (nums[low]+nums[high]) == sum){ 
                            res.push_back(vector<int>({ nums[i], nums[low], nums[high]}));
                            while( low < high && nums[low] == nums[low+1] ) low++;
                            while( low < high && nums[high] == nums[high-1] ) high--;
                            low++; high--;                        
                        }else if(nums[low]+nums[high] < sum) low++;
                        else high--;
                    }
                }
            }
            return res;
        }
    };

1.  首先传入数组进行排序，方便程序搜索；且返回的三元组要求也是排序的，所以对数组排序后更方便。
2.  每次for循环里，负责寻找三元组里面，第一个元素必须为`nums[i]`的三元组。这样搜索肯定不会漏。
3.  `low`和`high`分别往反方向前进，对于连续重复元素，程序只会使用其前进方向上第一个元素用来判断，之后的都会跳过（for循环里的第一个if判断，和两个子while循环）。
4.  for循环里的第一个if判断——在程序分析三元组第一个元素为nums\[i\]，如果nums\[i\]后有重复元素，那么这些重复元素都需要跳过，因为都是重复的分析。就算考虑到nums\[i\]和nums\[i+1\]是一样的，且某个三元组的前两个就是它俩，那么在第一次分析到nums\[i\]后，后面while循环会帮忙寻找到这个三元组的。（没有这个会导致集合里有重复的三元组）
5.  两个子while循环——既然都到了这两个子while循环，说明之前刚加入了一个新找到的三元组，接下来请看下一点。
6.  当`if( (nums[low]+nums[high]) == sum)`判断成功后，为了避免加入重复的三元组，则需要将low和high往对方方向前进到不重复的元素为止，所以首先这里执行两个子while循环（若没有连续重复，则不会执行）；然后需要执行`low++; high--;`，因为刚才`nums[low]+nums[high]`刚好等于`sum`，如果你这里只变一个，那么这二者要么会变得比sum大一点，要么小一点，这两种情况都不能找到三元组，所以不如两个都变化。
7.  `if(nums[low]+nums[high] < sum)`判断进入后，说明小了，因为nums\[low+1\]>=nums\[low\]，所以让low加1，使得`nums[low]+nums[high]`有可能等于`sum`。反之，就让high减一。
8.  我觉得这个思路的精髓还是在于使用排序数组，之前说了，每次for循环里，负责寻找三元组里面，第一个元素必须为`nums[i]`的三元组。但剩下两个元素的位置是用双向搜索来确定，程序确定的剩余两元素的位置，必然不会是所有的可能性。但关键就在于，剩余两元素的位置选择不用穷举，用这种双向扫描的方法，可以忽略掉不需要扫描的位置可能（根据二者大小来比较）。
9.  注意for循环里要写成`i<nums.size()`，而不要写成`i<nums.size()-2`，写成后者本是合理的，意思就是要预留出两个位置，因为是三元组嘛，但`nums.size()`返回的是无符号数，有符号数和无符号数比较，运算结果会转换成无符号数，当运算结果是负数就会发生错误。比如size是1,1 - 2 = -1，-1的位表示必须是每位bit都是1，但转换成无符号数后，就会成为无符号数的最大值。  
    也不用预留两个位置，因为`while(low < high)`判断后，数组长度<2的情况都会使得这个判断进不去。

# 优化 #

class Solution { 
    public:
        vector<vector<int>> threeSum(vector<int>& nums) { 
            sort(nums.begin(), nums.end());
            vector<vector<int>> res;
            for(int i=0;i<nums.size();i++){ 
                if( i==0 || (i > 0 & nums[i] != nums[i-1]) ){ 
                    int low = i+1; int high = nums.size()-1;
                    int sum = - nums[i];
                    if (sum < 0) break;
                    while(low < high){ 
                        if( (nums[low]+nums[high]) == sum){ 
                            res.push_back(vector<int>({ nums[i], nums[low], nums[high]}));
                            while( low < high && nums[low] == nums[low+1] ) low++;
                            while( low < high && nums[high] == nums[high-1] ) high--;
                            low++; high--;                        
                        }else if(nums[low]+nums[high] < sum) low++;
                        else high--;
                    }
                }
            }
            return res;
        }
    };

加一句`if (sum < 0) break;`，如果sum小于零，那么nums\[i\]大于零，那么说明后面的元素再怎么加起来也肯定不能使和等于零。因为后面的元素更大。

[Concise O_N_2_ Java solution]: https://leetcode.com/problems/3sum/discuss/7380/Concise-O%28N2%29-Java-solution
[LeetCode]: https://blog.csdn.net/anlian523/article/details/89682833