3 Sum

编号 : 15      
难度 : <font color="orange">Medium</font>

# 题目 :  
>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.
>
>**Note**:
>
>The solution set must not contain duplicate triplets.
>
>**Example**:
>
>>```
>>Given array nums = [-1, 0, 1, 2, -1, -4],
>>
>>A solution set is:  
>>[  
>>  [-1, 0, 1],  
>>  [-1, -1, 2]  
>>]
>>```

# 解 :  
```Cpp
class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> ret;
        
        /* 为了优化搜索过程，对数据进行排序，同时可以避免重复 */
        sort(nums.begin(), nums.end());
        
        for(int a = 0; a < nums.size();)
        {
            // 由于已经排序了a < b < c，
            // 所以如果0 < a，则必然有a+b+c > 0
            if(nums[a] > 0)
            {
                break;
            }
            // b和c从两头往中间找
            int b = a + 1;
            int c = nums.size() - 1;
            while(b < c)
            {
                int sum = nums[b] + nums[c];
                if(sum < -nums[a])
                {
                    b++;
                }
                else if(sum > -nums[a])
                {
                    c--;
                }
                else
                {
                    // 插入一组结果
                    ret.push_back({nums[a], nums[b], nums[c]});
                    
                    // 跳过重复
                    for(;b < c && nums[b] == nums[b+1]; b++);
                    for(;b < c && nums[c] == nums[c-1]; c--);
                    // 需要再移动一次
                    b++;
                    c--;
                }
            }
            
            // 跳过重复数据
            for(;a < nums.size() - 1 && nums[a] == nums[a+1]; a++);
            // 需要再移动一次
            a++;
        }
        
        return ret;
    }
};
```

# 分析 :  
三层循环嵌套遍历a、b、c，得出全部结果的复杂度为O(n^3)。除此外，判断是否重复也需要消耗大量的时间。因此必须进行优化。  

上面的解法首先把问题从`a + b + c = 0`转换为`b + c = -a`的问题。
将数组排序，并将`b`和`c`分别放在剩余搜索范围的两端，设`sum = b + c`，
则需要增大`sum`时只能将`b`向后移动，反之则只能将`c`向前移动，
这样一来对`b`和`c`的搜索复杂度从`O(n^2)`优化为了`O(n)`，
整个算法的复杂度变成了`O(n^2)`，同时由于排了序，可以轻松的跳过重复解。

另外，根据LeetCode题目上的三条hide hint，使用哈希表也能写出一些解法，例如下面的代码，但是下面的代码依然`Time Limit Exceeded`了。

```Cpp
class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> ret;
        
        /* 为了避免重复，对数据进行排序 */
        sort(nums.begin(), nums.end());
        
        /* 用来查找 */
        unordered_set<int> values_set;
        
        for(size_t a = 0; a < nums.size();)
        {
            values_set.clear();
            for(size_t c = a + 1; c < nums.size();)
            {
                /* 减去第一个值和最后一个值，来搜索中间的那个值
                 * 这样向map中插入值的操作可以放在每次查找之后
                 * 我刻意在变量名上使用a和c而跳过b，使其更加直观
                 */
                int value_b = 0 - nums[a] - nums[c];
                auto n = values_set.find(value_b);
                if(value_b < nums[a+1])
                {
                    // n比第一个可取值小，不可能有解，直接跳过
                    break;
                    
                }
                else if(value_b > nums[c-1] || n == values_set.end())
                {
                    // 保存map并继续循环
                    values_set.insert(nums[c]);
                    c++;
                    continue;
                }
                
                // 保存结果
                ret.push_back({nums[a], nums[c], value_b});
                
                // 跳过重复数据
                int value_c = nums[c];
                for(; c < nums.size() && value_c == nums[c]; c++);
            }
            
            // 跳过重复数据
            int value_a = nums[a];
            for(; a < nums.size() && value_a == nums[a]; a++);
        }
        
        return ret;
    }
};
```
* 根据该题下的3个隐藏提示，使用哈希表缓存数据，然而还是`Time Limit Exceeded`了。