LeetCode 15

概述

• https://leetcode-cn.com/problems/3sum
• 从一个数组中，找到所有的三个不同位置的数字，相加等于0
• 返回所有的相加等于0的三个数字，且结果不重复

思路

• 理解题目要求，三个数字位置要不同,三个数字组成的结果不重复，最后按组返回所有的三个数字

• 返回最终集合不能重复，所以这题不好用哈希法，因为哈希会把所有的结果都选出来，那么就可能三个数字组成的集合是重复的

  所以，考虑多指针法，而正好题目只需我们返回最终的值，那么可以将数据排序

• 如何确定指针数？

  • 首页一个排好序的数组，指针的移动方向就两个——前、后，所以移动指针可以有两个
  • 这题要求选三个，所以我们当然要选三个指针指向最终的结果

• 如何去重？

  • 因为排好序，所以相同的数据都集中在一起，只需判断此时的数据和之前的数据是否相同

    如果相同，则不处理该数据；

  class Solution {
  public:
      vector<vector<int>> threeSum(vector<int>& nums) {
          vector<vector<int>> result;
          sort(nums.begin(),nums.end());	//排序
          int L=nums.size();
          for(int i=0;i<L;i++){
              if(nums[i]>0)	//剪枝
                  break;
              int j=i+1;
              int k=L-1;
              if(i>0&&nums[i]==nums[i-1]) continue;	//去重
              while(k>j){
                  if(nums[i] + nums[j] + nums[k]>0)	//移动指针
  					k--;
  				else if(nums[i] + nums[j] + nums[k]<0)
  					j++;
  				else{
  					result.push_back(vector<int>{nums[i], nums[j], nums[k]});	//获得结果
  					while(nums[k]==nums[k-1]&&k>j)   k--;	//去重
                      while(nums[j]==nums[j+1]&&k>j)   j++;
  					//继续寻找
                      j++;
                      k--;
  				}
              }
  
          }
          return result;
      }
  };