2020字节跳动的社招算法 三数之和

引言  

给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有满足条件且不重复的三元组。

1：通过双循环 + 二分查找算法获取结果

1 public List<List<Integer>>  threeSum1(int[]  nums){ 2         List<List<Integer>> result=new ArrayList(); 3         if(null==nums || nums.length<=3){ 4           return result; 5         } 6         //先对数组排序 7         Arrays.sort(nums); 8         //通过双循环+二分查找获取结果 9         for(int beginIndex= 0 ; beginIndex < nums.length-2 && nums[beginIndex]<=0;beginIndex++){10            if(beginIndex>0 && nums[beginIndex]==nums[beginIndex-1]) continue;//已经匹配过的元素直接跳过11             for(int endIndex=nums.length-1 ; endIndex > beginIndex+1 && nums[endIndex]>=0;endIndex--){12                 if(endIndex<(nums.length-1) && nums[endIndex]==nums[endIndex+1]) continue;//已经匹配过的元素直接跳过13                 int temp=-(nums[beginIndex]+nums[endIndex]);14                 int searchIndex=Arrays.binarySearch(nums,beginIndex+1,endIndex,temp);15                 if(searchIndex>0){16                     result.add(new ArrayList<Integer>(Arrays.asList(nums[beginIndex],nums[endIndex],nums[searchIndex])));17                 }18             }19         }20         return result;21     }

1 package com.svse.test; 2 import java.util.ArrayList; 3 import java.util.Arrays; 4 import java.util.List; 5  6 public class SuanFaSum { 7  8     public static void main(String[] args) { 9          int[]  nums = {-1, 0, 1, 2, -1, -4, -2};10          SuanFaSum sum=new SuanFaSum();11          long start=System.currentTimeMillis();12          List<List<Integer>> allOptions=sum.threeSum1(nums);13          System.out.printf("数组%s 中三数之和为0的组合有：\n",Arrays.toString(nums));14          for(List<Integer> option:allOptions){15              System.out.printf("%s \n",option); 16          }17          long end=System.currentTimeMillis();18          System.out.println("用时："+(end-start)+"毫秒");19 20     }21 }

2：双索引搜索算法

1 public List<List<Integer>>  threeSum2(int[]  nums) { 2         List<List<Integer>> result = new ArrayList(); 3         if (null == nums || nums.length <= 3) { 4             return result; 5         } 6         //先对数组排序 7         Arrays.sort(nums); 8         //双索引搜索算法 9         for(int i=0;i<nums.length-2 && nums[i]<=0;i++){10             if(i>0 && nums[i]==nums[i-1]) continue;//已经匹配过的元素直接跳过11             int beginIndex=i+1;12             int endIndex=nums.length-1;13             while (beginIndex<endIndex){14                 if(beginIndex>(i+1) && nums[beginIndex]==nums[beginIndex-1]){15                     beginIndex++;16                 }17                 if(endIndex <(nums.length-1) && nums[endIndex]==nums[endIndex+1]){18                     endIndex--;19                 }20                 int temp=nums[i]+nums[beginIndex]+nums[endIndex];21                 //根据当前三个数的和，判断是起始索引向后移动还是结束索引向前移动，如果为0，则两个索引同时移动22                 if(temp>0){23                     endIndex--;24                 }else if(temp<0){25                     beginIndex++;26                 }else{27                     result.add(new ArrayList<Integer>(Arrays.asList(nums[i],nums[beginIndex],nums[endIndex])));28                     beginIndex++;29                     endIndex--;30                 }31             }32         }33 34         return result;35     }

1 package com.svse.test; 2 import java.util.ArrayList; 3 import java.util.Arrays; 4 import java.util.List; 5  6 public class SuanFaSum { 7  8     public static void main(String[] args) { 9          int[]  nums = {-1, 0, 1, 2, -1, -4, -2};10          SuanFaSum sum=new SuanFaSum();11          long start=System.currentTimeMillis();12          List<List<Integer>> allOptions=sum.threeSum2(nums);13          System.out.printf("数组%s 中三数之和为0的组合有：\n",Arrays.toString(nums));14          for(List<Integer> option:allOptions){15              System.out.printf("%s \n",option); 16          }17          long end=System.currentTimeMillis();18          System.out.println("用时："+(end-start)+"毫秒");19 20     }21 }