알 리 바 바 그룹 2017 여름 실습 자바 연구개 발 엔지니어 온라인 프로 그래 밍 문제

저 는 대학 3 학년 입 니 다. 최근 에 실습 을 찾 고 싶 습 니 다. 알 리 가 인턴 을 모집 하고 있 는 것 을 보고 알 리 의 2018 여름 자바 실습 을 준비 하기 시 작 했 습 니 다. 2017 여름 자바 실습 온라인 프로 그래 밍 문 제 를 볼 때 9 우 2 호 의 힘 을 들 여 문 제 를 완 성 했 습 니 다.아래 의 해법 은 본인 이 문제 가 없다 고 생각 합 니 다. 여러분 께 서 잘못된 방향 을 지적 해 주시 면 감사 하 겠 습 니 다!제목: 하나의 정형 (비 마이너스) 배열 로 나 누 어 전체 와 같은 4 개의 절편 으로 나 누 었 다. 예 를 들 어 {2, 5, 1, 1, 1, 1, 4, 1, 7, 3, 7}, 절편 작업 후 나 누 었 다. {2, 5}, {1, 1, 4}, {7} 도 이른바 4 등분 점 을 찾 았 다. 절 점 은 각각 1, 1, 3 이 고 절 점 은 전체 안에 있 지 않다.출력 을 나 눌 수 있 습 니까?시간의 복잡 도와 공간의 복잡 도 를 o (n) 로 요구한다.
사고: 1. 배열 을 먼저 2 등분 하고 l, r 로 기록 합 니 다. 그 중에서 l 은 수치 첫 번 째 요소 로 표 시 됩 니 다. r 는 배열 의 마지막 요소 로 표 시 됩 니 다.2. l 을 확대 하거나 r 를 줄 여 좌우 두 단락 을 똑 같이 하고 lsum 이 라 고 기록 하 며 똑 같 지 않 으 면 구분 할 수 없고 그렇지 않 으 면 세 번 째 단 계 를 진행한다.3. 남 은 중간 배열 의 동 리 를 세그먼트 로 나 누 어 ml = l + 2;mr = r-2。두 번 째 단계 와 유사 한 조작 을 하여 좌우 두 단락 이 같은 합 을 얻어 mlsum 이 라 고 기록 합 니 다.4. lsum = = mlsum 이면 나 눌 수 있 고 그렇지 않 으 면 나 눌 수 없다.다음은 코드:

package com.alibaba.interview;

public class FourPoint {
    public static boolean isFourPoint(int[] a) {
        //        
        int l = 0, r = a.length - 1;
        int lsum = a[0], rsum = a[a.length - 1];
        //          
        while (true) {
            //       ，    
            if (l == r) {
                return false;
            }
            if (lsum > rsum) {
                --r;
                rsum = rsum + a[r];
            } else if (lsum < rsum) {
                l++;
                lsum = lsum + a[l];
            } else {
                break;
            }
        }
        //     
        int ml = l + 2;
        int mr = r - 2;
        int mlsum = a[ml];
        int mrsum = a[mr];
        while (true) {
            //          ，    
            if (ml == mr) {
                return false;
            }
            if (mlsum > mrsum) {
                --mr;
                mrsum = mrsum + a[mr];
            } else if (mlsum < mrsum) {
                ml++;
                mlsum = mlsum + a[ml];
            } else {
                break;
            }
        }
        if (mlsum == lsum) {
            l++;
            ml++;
            r--;
            System.out.println("   ：" + a[l] + "," + a[ml] + "," + a[r]);
            return true;
        }
        return false;
    }

    public static void main(String[] args) {
        int[] a = { 2, 5,1, 1, 4, 1, 7, 3, 7 };
        if (FourPoint.isFourPoint(a)) {
            System.out.println("    ");
        } else {
            System.out.println("     ");
        }
    }
}