題目描述
????給定一個(gè)整數(shù)數(shù)組datas和一個(gè)整數(shù)sum淤击，判斷數(shù)組中是否存在三個(gè)數(shù)的和為sum，存在輸出True，不存在則輸出False妥泉。
解題思路
????最容易想到的解法就是三層循環(huán)遍歷判斷，暴力解法洞坑，時(shí)間復(fù)雜度為O(n^3)盲链。這里我們改進(jìn)下算法，算法思路對(duì)應(yīng)偽代碼如下：外部一層循環(huán)迟杂，內(nèi)部頭尾指針同時(shí)移動(dòng)刽沾，時(shí)間復(fù)雜度為nlog(n)
for i in 0 to datas.length
int j=i+1;
int k=datas.length-1;
int currentSum=dadas[i]+datas[j]+datas[k];
while(currentSum!=sum&&j<k){
if(currentSum<sum){
currentSum=dadas[i]+datas[++j]+datas[k];
}else if(currentSum>sum){
currentSum=dadas[i]+datas[j]+datas[--k];
}
if(currentSum==sum) return "True"
}
return "False"
Java代碼實(shí)現(xiàn)
import java.util.Arrays;
import java.util.Collections;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
String[] lineStr=sc.nextLine().split(",");
String[] numStrs=lineStr[0].split(" ");
Integer[] nums=new Integer[numStrs.length];
for(int i=0;i<numStrs.length;i++){
nums[i]=Integer.valueOf(numStrs[i]);
}
Integer sum=Integer.valueOf(lineStr[1]);
System.out.println(solution(nums, sum));
}
// public static String solution(Integer[] nums,int sum) {
// String isExist="False";
// for(int i=0;i<nums.length-2;i++){
// for(int j=i+1;j<nums.length-1;j++){
// for(int k=j+1;k<nums.length;k++){
// if(nums[i]+nums[j]+nums[k]==sum){
// isExist="True";
// break;
// }
// }
// }
// }
// return isExist;
// }
public static String solution(Integer[] nums,int sum) {
String isExist="False";
Arrays.sort(nums);
for(int i=0;i<nums.length-2;i++){
int index1=i+1;
int index2=nums.length-1;
int currentSum=nums[i]+nums[index1]+nums[index2];
while(index1<index2&¤tSum!=sum){
if(currentSum<sum){
currentSum=nums[i]+nums[++index1]+nums[index2];
}else if (currentSum>sum) {
currentSum=nums[i]+nums[index1]+nums[--index2];
}
if(currentSum==sum){
isExist="True";
break;
}
}
}
return isExist;
}
}
