记一次算法：leetcode中第15号题（3num）

 题目要求：给出一个整型数组，寻找其中所有不同的三元组（a，b， c）使得a+b+c = 0；

    因为刚学了map和set容器，所以还是用map来解决这个问题。

    首先我们来看看题目给出的类的代码：

    class Solution {

public:

    vector<vector<int>> threeSum(vector<int>& nums) {

       

    }

};

    要求是输入一个vector<int> 型的元素，返回的是vector<vector<int>> 型的元素。

下面是我写的c++源码

 using namespace std;

class Solution {
public:
    vector> threeSum(vector& nums) {
        multimap m;
        vector> a;
        for(int i = 0; i < nums.size(); i++){//map自动升序排列
            m.insert(pair (nums[i], i));
        }
        vector> vec_2int(m.begin(), m.end());
        // sort(vec_2int.begin(), vec_2int.end(), CompareFirst());
        int i = 0, j = nums.size() - 1;
        while(j - i > 2){
            int c = -vec_2int[i].first - vec_2int[j].first;
            if(c >= vec_2int[j].first){
                i ++;
            }else if(c <= vec_2int[i].first){
                j --;
            }else{
                int k = i + 1;
                while(j - k > 0){
                    if(vec_2int[k].first == c){
                        vector vec2 = {vec_2int[i].second, vec_2int[j].second, vec_2int[k].second};
                        a.push_back(vec2);
                    }
                    k++;
                    i++;
                    j--;
                }
            }
        }
        
        return a;
    }
private:
    struct CompareFirst {
    bool operator()(const pair& a, const pair& b){
        return a.first < b.first;
        }
    };
};

int main(){
    int a[] = {-1, 0, 1, 2, -1, -4};
    vector num(a, a + sizeof(a)/sizeof(int));
    vector> a1 = Solution().threeSum(num);
    for(auto x : a1){
        for(auto m : x){
            cout << m << " ";
        }
        cout << endl;
    }
    cout << endl;
    return 0;
}

    值得一提的是，这段代码其实跑不起来（哈哈哈哈）

由于写这段代码的年代过于久远（其实就是一个上午）我已经不想了解我写这段代码时的逻辑了。最后决定重新写一个。

class Solution {
  public:
      vector> threeSum(vector& nums) {
          vector> result;
          int n = nums.size();
          sort(nums.begin(), nums.end());

          for (int i = 0; i < n - 2; ++i) {
              if (i > 0 && nums[i] == nums[i - 1]) 
                  continue;

              int left = i + 1, right = n - 1;
              while (left < right) {
                  int sum = nums[i] + nums[left] + nums[right];
                  if (sum == 0) {
                      result.push_back({nums[i], nums[left], nums[right]});
                      while (left < right && nums[left] == nums[left + 1]) left++;
                      while (left < right && nums[right] == nums[right - 1]) right--;
                      left++;
                      right--;
                  } else if (sum < 0) {
                      left++;
                  } else {
                      right--;
                  }
              }
          }

          return result;
      }
  };
	
	

    这个代码中没有使用map容器，而是简单地使用了vector<vector<int>>作为保存数组的容器和输出的结果。

    代码的实现原理

首先在类中定义了一个vector<vector<int>>型的变量result用来存放结果。

而后用一个int型的变量来储存nums的大小（用来遍历nums）

再后就是对nums向量以从小到大的顺序排序

sort(nums.begin(),nums.end());

 要注意：sort算法只能用于vector容器而不能用于map，set容器（其实map和set容器都是插入后就帮你把顺序排好了的）在c++语言中set和map的底层实现是平衡二叉树，unordered_map,unoredered_set的底层实现是哈希表，哈希表的搜索、查找、删除的时间复杂度都是O（1）但是失去了数据的顺序性。

第4个代码是一个循环（循环退出条件为i < n - 2即小于nums向量的最大下标），循环中整个代码的主体核心：

    第1句是判断语句，判断i是否大于0且nums[i]是否与nums[i - 1]相同，如果为真，则跳过此次的循环（直接i++）从而避免nums向量中的元素重复的问题。

    第2句定义了两个索引lleft和right开始对整个数组进行操作（根据题目的要求）在索引定义后又有一个循环（一般在定义索引后都会有一个循环。循环里设置的变量为局部变量，只在循环的内部有效，可以重复定义和使用，不会受上一次循环的影响。）

    循环内部定义的局部变量为int型的sum用来储存三个数的和。

    而后就又出现了一条判断语句，用以判断sum的值是否为“0”。如果为“0”则result（vector<vector<int>>型）后添加一个vector<int>向量，向量中有3个int型数据，分别为nums[i]，nums[left]，nums[right]。

    而后为避免数据重复又新增两条判断语句

    

while (left < right && nums[left] == nums[left + 1]) left++;
while (left < right && nums[right] == nums[right - 1]) right--;（没错，while也是判断语句，而且是一旦执行就一直处理到不满足的判断语句）

    再后就是两个索引的移动

如果不满足条件又判断sum是否小于0，小于则left索引右移，否则right索引左移。

    循环执行完毕后输出result