《剑指offer》Java实现--判断数组中是否存在和为指定值的

题目描述

    给定一个整数数组datas和一个整数sum，判断数组中是否存在三个数的和为sum，存在输出True，不存在则输出False。

解题思路

    最容易想到的解法就是三层循环遍历判断，暴力解法，时间复杂度为O(n^3)。这里我们改进下算法，算法思路对应伪代码如下：外部一层循环，内部头尾指针同时移动，时间复杂度为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代码实现

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&&currentSum!=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;
    }

}