首页 > 代码库 > 数组切片算法
数组切片算法
题目如下:就是一个数组,切三刀,从这三个切口组成的四个切片的整数和是否能够四等分,如果可以,就返回true,不行就返回false。
主要的思路就是记着三个切点为m1,m2,m3(和是不包括m1 m2 和m3的),则先找m1,m2,头尾的和相等后,记为count,利用count以及m1,m3来查找m2。其中的细节在于,第一次找到的count不一定是对的,这样需要扩大count 继续寻找。具体代码如下。
代码实现如下
1 package p2; 2 3 public class ali { 4 5 // 数组切片。 6 public boolean fun (int [] A){ 7 int len=A.length; 8 if(len<=3) return false; 9 int i=0;int j=len-1; 10 int count1=A[i]; 11 int count2=A[j]; 12 boolean check; 13 while(i<j){ 14 if(count1<count2){ 15 i++; 16 count1+=A[i]; 17 } 18 if(count1>count2){ 19 j--; 20 count2+=A[j]; 21 } 22 else{ 23 i++; 24 j--; 25 check=check( A,i,j,count1); 26 if(check){ //如果找到了m2 直接返回true 27 return check; 28 } 29 else{ 30 count1+=A[i]; //如果找不到符合条件的m2 则增大count 继续查找 31 count2+=A[j]; 32 33 } 34 } 35 36 } 37 return false; 38 } 39 public boolean check(int [] A,int i,int j,int sum){ 40 int l =i+1; 41 int r=j-1; 42 int left=A[l],right =A[r]; 43 while(l<r){ 44 if(left<right){ 45 l++; 46 left+=A[l]; 47 } 48 if(left>right){ 49 r++; 50 right+=A[r]; 51 } 52 else if(left==right){ 53 if(left==sum&&r-l==2){ //注意这里的条件 找到的r 和l相当于m2+1和m2-1 相差2这个条件需要满足 54 return true; 55 } 56 if(left<sum){ //如果比传进来的sum小的话就增加和 57 l++;left+=A[l]; 58 r--;right+=A[r]; 59 } 60 else return false; //都不满足的话 就就表示无法找到 可能需要增加上一级的count或者是不满足条件了。 61 } 62 } 63 return false; 64 65 } 66 }
数组切片算法
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。