题目描述

给定一个f整数数组 arr，判断能否将该数组划分为 n部分(n为正整数），每部分包含至少一个元素，且各部分元素的和相等。

eg：
input：arr: [1,1,1], n: 3
output: true

解法

点击查看

/**
 * @param {Array} arr
 * @param {int} n
 * @return {Bool}
 * 
 */
 function solution(arr, n){
	const sum = arr.reduce((acc, curr)=>acc+curr, 0);
	const p = sum / n;
	if(p !== parseInt(p)){
		return false;
	}
	let i = 0;
	let acc = 0;
	while(i < arr.length && n > 0){
		acc += arr[i];
		if(acc !== p){
			i++;
		}else{
			n--;
			acc = 0;
			i++;
		}
	}
    while(n === 0 && i < arr.length){ //处理末尾 0元素
		if(arr[i] !==0){
			break;
		}
		i++;
	}
	if(n === 0 && i === arr.length){
		return true
	}
	return false
 }

总结

阿里三面时现场给我出的一道题，是划分数组为 K个和相等的子集的简化版。 主要切入点在于求和求平均值。