欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

将数组分为4个子数组,且它们的和相等

程序员文章站 2024-02-03 17:06:40
...

这是一道某名企的开发实习岗的在线笔试题,题目描述是这样的:

输入为一个int类型的数组,在数组中选择三个切割点,将该数组分为四个子数组(不包含切割点),若这四个子数组的和相等,则返回true, 否则返回false.

例如:

Input : [3, 2, 4, 1, 4, 9, 5, 10, 1, 2, 2]

Output : true. (三个切割点下标为2, 5, 7. 四个子数组为[3,2], [1,4], [5], [1,2,2])


Input : [1, 2, 4, 2, 4, 5, 6, 1, 2, 3]

Output : false.

要求时间复杂度为O(n), 空间复杂度为O(n).


解题思路:

时间复杂度为O(n), 所以不能采用暴力求解。先设两个指针i, j,i 指向数组头,j指向数组尾部,维护leftSum = sum[0]+..sum[i], rightSum = sum[j]  + ... sum[a.length-1]。若leftSum < rightSum , 则 i++, 更新leftSum; 若leftSum > rightSum, 则j--, 更新rightSum. 一直重复此步骤,直到leftSum = rightSum或i>=j停止,若i>=j,则返回false, 若leftSum  = rightSum, 说明暂时找到了第一和第三个切割点,现在要在i, j之间找第二个切割点,这时我们可以利用HashMap在O(1)的时间复杂度内判断能否找到第二个合法的切割点。方法如下:HashMap里放的键值对为(sum[i],i). 其中sum[i]代表数组a从第0个位置到第i个位置的元素之和。这样我们可以在leftSum = rigthSum的基础下, 用map.get(leftSum + a[first_index] + leftSum)来返回第二个切割点的下标,若不存在或者返回的下标seconde_index >= third_index, 则寻找失败,继续下一次探测,否则找到第二个切割点,返回true.

Java代码如下:

public static boolean ifExistFourEquals(int[] arr){
        int len = arr.length;
        if(len < 7) {
            System.out.println("can not split it into four equals!");
            return false;
        }
        int[] sum = new int[len];
        Map<Integer,Integer> map = new HashMap();
        sum[0]=arr[0];
        map.put(sum[0],0);
        for(int i =1;i<len;i++){
            sum[i]=sum[i-1]+arr[i];
            map.put(sum[i],i);
        }
        int first_index = 0;
        int third_index = len-1;
        int leftSum = arr[0];
        int rightSum = arr[len-1];
        while(true) {
            while (leftSum != rightSum && first_index < third_index) {
                while (leftSum < rightSum) {
                    ++first_index;
                    leftSum += arr[first_index];
                }
                while (leftSum > rightSum) {
                    --third_index;
                    rightSum += arr[third_index];
                }
            }
            if(first_index >= third_index) {
                System.out.println("can not split it into four equals!");
                return false;
            }
            //leftSum == rightSum
            else {
                ++first_index;
                --third_index;
                if(!map.containsKey(leftSum+arr[first_index]+leftSum)){
                    leftSum += arr[first_index];
                    rightSum += arr[third_index];
                    continue;
                }
                else{
                    int second_index = map.get(leftSum + arr[first_index] + leftSum);
                    //失败,继续下一次探测
                    if(second_index >= third_index){
                        leftSum += arr[first_index];
                        rightSum += arr[third_index];
                        continue;
                    }
                    else{
                        if(sum[second_index] - sum[first_index] == leftSum &&
                                sum[third_index-1] - sum[second_index+1] == rightSum){
                            ++second_index;
                            System.out.println("Index 1:" + first_index +";\nIndex 2:" + second_index +";\nIndex 3:"+third_index);
                            return true;
                        }
                    }
                }
            }
        }
    }