题解 | 数组中相加和为0的三元组

解法一：双指针

• 对数组长度进行特判

• 排序

  • num[i]>0说明后面的三数和不可能等于0。
  • 对于重复元素跳过
  • 左指针left=i+1，右指针right = len-1
  • 当nums[i]+nums[left]+nums[right]==0执行循环，判断左界和右界是否和下一位置重复，去除重复解。并同时将 left,right 移到下一位置，寻找新的解.
  • 如果和<0left++;
  • 如果和>0):right--；
  • 图解：
    

Java参考代码：

import java.util.*;
  public class Solution {

      public ArrayList<ArrayList<Integer>> threeSum(int[] num) {
            //存放最终答案的二维数组
          ArrayList<ArrayList<Integer>> ans = new ArrayList<>();
          int len = num.length;
           //特判：长度<3的数组不满足条件
          if(len<3){
              return ans;
          }
          //排序O(nlogn)
          Arrays.sort(num);

          for(int i=0;i<len;i++){
            //如果nums[i]已经大于0，就没必要继续往后了，因为和就是0啊
              if(num[i]>0){
                  return ans;
              }
              //注意考虑越界i>0,主要功能是排除重复值
              if(i>0 && num[i]==num[i-1]){
                  continue;
              }
              //声明指针
              int cur = num[i];
              int left = i+1;
                //从尾部开始
              int right =len-1;
              while(left<right){
                //满足条件的三数和
                  int tp_ans = cur+num[left]+num[right];
                //如果已经找到和为0
                 if(tp_ans==0){
                    //创建一个数组，并将满足条件的三元素放进去
                     ArrayList<Integer> list = new ArrayList<>();
                     list.add(cur);
                     list.add(num[left]);
                     list.add(num[right]);
                    //将最终的结果存入答案数组ans中
                     ans.add(list);
                     //判断是left指针指向是否重复