Shoppe笔试4.15 编程题1.5/3
第一道：先跳过了后来也没来得及回来做
第二题：算出所有加起来等于0的序列，我真的很纳闷，这是一道典型的三数之和的题目，用排序+ 双指针做可以把时间复杂度从O(n ^3)变成O(n ^ 2), 然而当我信心慢慢以为要AC的时候，竟然只过了百分之60？不知道各位大佬是怎么做的？能不能跟我分享一下思路，这题还需要更优解吗
下面是代码
package Testing;
import java.util.*;
import javax.xml.soap.Node;
public class Main
{
public static void main(String [] args)
{
Scanner scan = new Scanner(System.in);
String input = scan.nextLine();
String[] arr = input.split(",");
int[] numberArr = new int[arr.length];
ArrayList<ArrayList<Integer>> output = new ArrayList<ArrayList<Integer>>();
for(int i = 0; i < arr.length; i++)
numberArr[i] = Integer.parseInt(arr[i]);
Arrays.sort(numberArr);
for(int i = 0; i < numberArr.length - 2; i++)
{
int left = i + 1;
int right = numberArr.length - 1;
while(left < right)
{
int sum = numberArr[i] + numberArr[left] + numberArr[right];
if(sum == 0)
{
ArrayList<Integer> temp = new ArrayList<Integer>();
temp.add(numberArr[i]);
temp.add(numberArr[left]);
temp.add(numberArr[right]);
output.add(temp);
left++;
right--;
}
else if(sum > 0)
right--;
else if(sum < 0)
left++;
}
}
String finaloutput = "";
finaloutput += output.get(0);
for(int i = 1; i < output.size() - 1;i++)
finaloutput += "," + output.get(i);
System.out.print(finaloutput.replace(" ", ""));
}
} 第三题：经典的机器人行走DP问题，直接AC
