LeetCode算法题——给定数组求可满足的三元组

mac2022-09-22  27

题目

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

注意:答案中不可以包含重复的三元组。

例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4],

满足要求的三元组集合为: [   [-1, 0, 1],   [-1, -1, 2] ]  

代码实现

public class demo { public static HashMap<String,Integer> findTriple(HashMap<Integer,Integer> map1,HashMap<Integer,Integer> map2) { int result_index = 0; HashMap<String,Integer> last_over = new HashMap<>(); String[] result = new String[100]; //第一个for循环表示map1的元素从左到右移动长度 for(int i=0;i<map1.size()-1;i++) { //第二个for循环表示选取map2的值 for(int j=0;j<map2.size();j++) { //第三个for循环表示取map1 i 位置后的元素 for(int k=i+1;k<map1.size();k++) { //判断语句让小的放在前面 if(map1.get(i)+map1.get(k)+map2.get(j)==0) { if(map1.get(i)<0) { result[result_index] = "["+map1.get(i)+","+map1.get(k)+","+map2.get(j)+"]"; result_index++; }else { result[result_index] = "["+map2.get(j)+","+map1.get(i)+","+map1.get(k)+"]"; result_index++; } } } } } //把重复元素去除 for(int i=0;i<result.length;i++) { if(result[i]!=null) { last_over.put(result[i],i); } } /* for(String key:last_over.keySet()) { System.out.println(key); }*/ return last_over; } public static void main(String[] args) { int[] first = {-1, 0, 1, 2, -1, -4}; Arrays.sort(first); System.out.println(); if(first[0]>=0) { System.out.println("该数组中不存在三元组"); }else if(first[first.length-1]<=0){ System.out.println("该数组中不存在三元组"); }else { HashMap<Integer,Integer> map1 = new HashMap<>(); HashMap<Integer,Integer> map2 = new HashMap<>(); int map1_index = 0; int map2_index = 0; for(int i=0;i<first.length;i++) { if(first[i]<0) { map1.put(map1_index,first[i]); map1_index++; }else { map2.put(map2_index, first[i]); map2_index++; } } int map2_0 = 0; for(int key:map2.keySet()) { if(map2.get(key)==0) { map2_0++; if(map2_0==3) { break; } } } HashMap<String,Integer> end1 = findTriple(map1, map2); HashMap<String,Integer> end2 = findTriple(map2, map1); ArrayList<String> over = new ArrayList<>(); for(String key:end1.keySet()) { over.add(key); } for(String key:end2.keySet()) { over.add(key); } if(map2_0==3) { over.add("["+0+","+0+","+0+"]"); } if(over.size()==0) { System.out.println("该数组中不存在三元组"); }else { System.out.println(over); } } } }

 

最新回复(0)