算法题：N个的整数数组，判断其中a,b,c三元素a+b+c=0的所有三元组，不允许重复

86 阅读 0 评论 57 点赞

我是靠谱客的博主贪玩皮卡丘，最近开发中收集的这篇文章主要介绍算法题：N个的整数数组，判断其中a,b,c三元素a+b+c=0的所有三元组，不允许重复，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

昨晚上面试了一家大厂，被要求刷这个题，20分钟左右时间没有完全写好，面试官是不允许用三个for循环做的，实在没想出其他方法，下午试了一下写了个死循环出来哎，我无语，然后调试了一下，结果还可以

import java.util.ArrayList;
import java.util.Arrays;

public class Solution {
   public static ArrayList<ArrayList<Integer>> findOutArray(int[] arr){
       int len = arr.length;
       if(arr==null || arr.length <=2) {
           return null;
       }
       Arrays.sort(arr);

       if(arr[0] > 0 || arr[len-1]<0) {
           return null;
       }
       int start = 0;
       int end = 0;
       ArrayList<ArrayList<Integer>> temp = new ArrayList<ArrayList<Integer>>();
       for(int i=0;i<len-2;i++) {
           start = i + 1;
           end = len - 1;
           while(start < end) {
                   while(start < end && arr[i] + arr[start] +arr[end] > 0 ) {
                       end--;
                   }
                   if(start < end && arr[i] + arr[start] + arr[end] == 0) {
                       ArrayList<Integer> list = new ArrayList<Integer>();
                       list.add(arr[i]);
                       list.add(arr[start]);
                       list.add(arr[end]);
                       temp.add(list);
                       end--;
                       System.out.println(list);
                   }
                   while(start < end && arr[start] == arr[start+1]) {
                       start++;
                   }
                   if(start <end && arr[i] + arr[start] +arr[end] < 0) {
                       start++;
                   }
               }
       }
       return temp;

   }

   public static void main(String[] args) {
       int[] a= {-3,-2,0,2,1,3};
       System.out.println(a.length);
       ArrayList<ArrayList<Integer>> result = findOutArray(a);
   printArray(result);

   }

   private static void printArray(ArrayList<ArrayList<Integer>> result) {
       // TODO Auto-generated method stub
       for(int i=0;i<result.size()-1;i++)
       System.out.println(result.get(i).stream().mapToInt(a->a));

   }

}

上面的解题思路还有点问题，下面是A过的：

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
      int n = nums.length;
        Arrays.sort(nums);
        List<List<Integer>> ans = new ArrayList<List<Integer>>();

        for (int first = 0; first < n; ++first) {
            if (first > 0 && nums[first] == nums[first - 1]) {
                continue;
            }
            int third = n - 1;
            int target = -nums[first];
            for (int second = first + 1; second < n; ++second) {
                if (second > first + 1 && nums[second] == nums[second - 1]) {
                    continue;
                }
                while (second < third && nums[second] + nums[third] > target) {
                    --third;
                }
                if (second == third) {
                    break;
                }
                if (nums[second] + nums[third] == target) {
                    List<Integer> list = new ArrayList<Integer>();
                    list.add(nums[first]);
                    list.add(nums[second]);
                    list.add(nums[third]);
                    ans.add(list);
                }
            }
        }
        return ans;
    }
}

输出是：
[-3, 0, 3]
[-3, 1, 2]
[-2, 0, 2]