题目
给定一个包含 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);
}
}
}
}