아 리 내 추 인턴 온라인 프로 그래 밍 문제

아 리 인턴 내 온라인 프로 그래 밍 문제
시험 후에 이 문제 에 관심 이 많아 서 시간 을 들 여 다시 한 번 해 보 았 습 니 다. 아 리 의 온라인 프로 그래 밍 문 제 는 모두 랜 덤 이 라 고 믿 습 니 다. 만약 여러분 이 나중에 이 문 제 를 풀 때 마침 이 문 제 를 만 났 다 면... 순 전 히 우연 의 일치 입 니 다.)

아 리 인턴 내 온라인 프로 그래 밍 문제

문제

사고방식

코드

의문

구유

제목.

       N     A,           ,     m1,m2,m3
(     0

사고의 방향
배열 의 첫 번 째 꼬리 양 끝 지침 low 과 high 을 설정 하고 슬라이스 1 - 4 의 합 은 sum1~sum4 이 며 low 과 high 을 가운데 로 붙 이 고 풀 리 면 반드시 high>low 의 상황 에서 sum1 == sum4 이 나타 날 것 이다.그러면 이때 우 리 는 곧 지 워 질 단점 i =low+1 과 j = low-1 을 기록 했다.그리고 우 리 는 똑 같은 방법 으로 sum3 == sum4 을 얻 었 다. 만약 에 적당 하 다 면 low+1 = high-1 을 얻 을 수 있다.그러면 sum1==sum2 을 판단 하면 해 가 있 는 지 아 닌 지 를 알 수 있 습 니 다. 그러면 이렇게 딱 좋 지 않 습 니 다.만약 에 Status 과 같은 방법 으로 우 리 는 지침 i 을 low 의 방향 으로 이동 시 켜 sum1 += A[i], sum2-=A[++i] 에서 sum1 < sum2 까지 처리 할 것 이다.이렇게 해서 우 리 는 다시 sum1 > sum2 ,sum2+= A[low++], sum1 == sum2 ; 의 상황 으로 돌 아 왔 다. 만약 j 이 라면 결 과 를 알 수 있 을 것 이다.
코드

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;

/**
 * @author Jiangjiaze
 * @version Id: AliExam .java, v 0.1 2017/3/7 22:34 FancyKong 
 */
public class AliExam {
    static boolean resolve(int[] A) {
        int low = 0;
        int high = A.length - 1;
        long sum1 = A[low];
        long sum4 = A[high];
        while (low != high)
            //        
            if (sum1 == sum4) {
                break;
            } else if (sum1 < sum4) {
                sum1 += A[++low];
            } else {
                sum4 += A[--high];
            }
        int i = low + 1; //            
        int j = high - 1;
        low += 2; //         
        high -= 2;
        if (low >= high) return false;
        //  ,        
        long sum2 = A[low];
        long sum3 = A[high];
        while (low != high) {
            if (sum2 == sum3) {
                break;
            } else if (sum2 < sum3) {
                sum2 += A[++low];
            } else {
                sum3 += A[--high];
            }
        }
        low++;
        high--;
        //  high     low ,          
        while (high > low) {
            while (high >= low) {
                //    ,sum1+   sum2 -;        low   i  
                sum1 += A[i];
                sum2 -= A[++i];
                while (sum1 > sum2) {
                    sum2 += A[low++];
                }

            if (sum1 == sum2) break;
        }
        while (high >= low) {
            //  
            sum4 += A[j];
            sum3 -= A[--j];
            while (sum4 > sum3) {
                sum3 += A[high--];
            }
            if (sum3 == sum4){
                //         break,     sum1 sum4   
                //      ,  sum1  sum4 break ;     sum4     
                if(sum1 == sum4 && low == high) return true;
                if(sum1 < sum4)
                    break;
              }
           }
        }
        return low == high && sum1 == sum2 && sum1 == sum3;
    }

    public static void main(String[] args) {
        //     main        .
        //          
        mainTest(null);
    }
    public static void mainTest(String[] args) {
        ArrayList inputs = new ArrayList();
        Scanner in = new Scanner(System.in);
        int n = in.nextInt(); //        ,  4  
        int random[] = new int[n];
        //         
        for (int i = 0; i < n; i++) {
            random[i] = (int)(100*Math.random());
        }
        int[] A = new int[4*n+3];
        System.arraycopy(random,0,A,0,n);
        System.arraycopy(random,0,A,n+1,n);
        System.arraycopy(random,0,A,2*n+2,n);
        System.arraycopy(random,0,A,3*n+3,n);
        //            ,           
        /*int div = A[n+1];
        A[2] -= div;
        A[n+3] +=div;
        A[n+1] = A[n];
        A[n] = div;*/
        System.out.println(Arrays.toString(A));
        Boolean res = resolve(A);

        System.out.println(String.valueOf(res));
    }
}

의문
정 답 인가요?본인 소 백, 이런 해법 은 O (n) 시간 복잡 도 라 고 할 수 있 습 니까?의문 이 있 으 면 나 와 교류 할 수 있다.
구유
아 리 인턴 채용 시스템 초 다 BUG...