苦于学了忘，忘了学，部门大佬给机会周会每周一道算法题开阔思维。该系列一边学码UML加深印象记住简单的算法逻辑，一边回顾算法。。。反正就随便记随便看吧。总结一下部门出的题
UML练习
FcsCodeOne.png
UMLCODE
@startuml
start
:FcsCodeOne.fcsCodeOne(int[] num);
note right
FCS算法题：给出一个整数数组，找出里面所有三个能够相加起来为0的元素(不可以有重复的三个元素的组合，例如:[-1,1,0]和[-1,0,1]是相同的，最终结果不可包含重复)
example:
S = [-1, 0, 1, 2, -1, -4,2,-2,4],
A solution set is:
[
[-1, 0, 1],
[-1, -1, 2]
]
end note
: List<List<Integer>> resultList=new ArrayList<List<Integer>>();
note right
前置限制num长度至少为3
存放结果的数据结构
end note
:Array.sort(num);
while (int z_index=0;z_index<num.length-2?) is (true)
note right
外层循环，z=x+y
z右侧必须有两个数的位置
end note
if (z_index=0||(z_index>0&&num[z_index]!=num[z_index-1])) then (yes)
note right
一开始是需要判断的
以及num[z_index]不等于前一个值的时候不需要去重的时候
就继续走
end note
:int x_index=z_index+1;
:int y_index=num.length-1;
:int sum=-num[z_index];
note right
z+x+y=0
-z=x+y
end note
while (x_index<y_index) is (true)
if (sum==num[x_index]+num[y_index])) then (yes)
note left
-z=x+y满足后
x y z存入List
记得去重x++ y--
end note
:List<Integer> result=new ArrayList<Integer>();
:result.add(num[z_index]);
:result.add(num[x_index]);
:result.add(num[y_index]);
:resultList.add(result);
while(x_index<y_index&&num[x_index]==num[x_index+1]) is(yes)
:x_index++;
endwhile
while(x_index<y_index&&num[y_index]==num[y_index-1]) is(yes)
:y_index--;
endwhile
:x_index++;
:y_index--;
elseif (sum>num[x_index]+num[y_index]) then (yes)
while(x_index<y_index&&num[x_index]==num[x_index+1]) is(yes)
:x_index++;
endwhile
:x_index++;
else (nothing)
while(x_index<y_index&&num[y_index]==num[y_index-1]) is(yes)
:y_index--;
endwhile
endif
endwhile (false)
else
:下一次循环;
endif
endwhile (false)
:输出结果;
stop
@enduml
答案CODE
/**
* Created by mori.wang on 2018/3/26.
*/
public class FcsCodeOne {
/**
* 题目：给出一个整数数组，找出里面所有三个能够相加起来为0的元素(不可以有重复的三个元素的组合，例如:[-1,1,0]和[-1,0,1]是相同的，最终结果不可包含重复)
example:
S = [-1, 0, 1, 2, -1, -4,2,-2,4],
A solution set is:
[
[-1, 0, 1],
[-1, -1, 2]
]
tip:
1.思路一 x+y=-z 两个数决定第三个数
三个数肯定有一个正或者一个负数
x 正
y z 可能是正或者是负
2.思路二 排序
...[-4,-2,-1,-1,0,1,2,2,4].....
| | |
z x y
3.去重
排序后，连续的游标（x）往后走的时候如果value跟之前的一样，那就不操作，继续++
（y）往前走的时候value一样 继续--
4.停止条件 （）
*/
public static void fcsCodeOne(int[] num){
//默认num输入有正有负哦 伪代码check(num)
List<List<Integer>> resultList=new ArrayList<List<Integer>>();//结果存放
Arrays.sort(num);//排序/DualPivotQuicksort快排 O(nlogn)
for(int z_index=0;z_index<num.length-2;z_index++){//最外层循环确定x 要三个数 所以第一个数指针最多在左二
if(z_index==0||(z_index>0&&num[z_index]!=num[z_index-1])){//一开始要进去，其次就是结束一次内循环后，要做次x的去重 比如 -1 -1 0 1 这种就要去重
//确定x 和y
int x_index=z_index+1;//x的下一位
int y_index=num.length-1;//z末尾
int sum=-num[z_index];//z=x+y
//内层循环 只要x<y就一直做处理 根据左右的大小来判断x移动还是y移动
while(x_index<y_index){
//如果刚好x=y+z
if(sum==num[x_index]+num[y_index]){
List<Integer> result=new ArrayList<Integer>(3);
result.add(num[z_index]);
result.add(num[x_index]);
result.add(num[y_index]);
resultList.add(result);
//记得去重
while(x_index < y_index && num[x_index] == num[x_index+1]){
x_index++;//去重 移动y
}
while(x_index < y_index && num[y_index] == num[y_index-1]){
y_index--;//去重 移动z
}
//
x_index++;
y_index--;
}else if(sum>num[x_index]+num[y_index]){//
while(x_index < y_index && num[x_index] == num[x_index+1]){
x_index++;//去重 移动y
}
//左边太大 记得右移的时候去重
x_index++;
}else{
//左移的时候去重
while(x_index < y_index && num[y_index] == num[y_index-1]){
y_index--;//去重 移动z
}
y_index--;
}
}
}
}
//
System.out.println(JSON.toJSONString(resultList));
}
public static void main(String[] args){
fcsCodeOne(new int[]{-1,0,1,2,-1,-4});
}
