给定一个无序数组arr,其中元素可正,可负,可0,给定一个整数k。求arr所有的子数组中累加和为k的最长子数组长度。
public static int maxSubArrLength(int[] arr ,int num){
if (arr == null || arr.length < 2) return 0;
HashMap<Integer,Integer> hashMap = new HashMap<>();
hashMap.put(0,-1);
int sum = 0;
int res = 0;
for (int i = 0 ; i < arr.length;i++){
sum += arr[i];
if (hashMap.containsKey(sum - num)){
res = Math.max(res,i -hashMap.get(sum - num));
}if (!hashMap.containsKey(sum)){
hashMap.put(sum,i);
}
}
return res;
}
1. 给定一个无序数组arr,其中元素可正,可负,可0。求arr所有的子数组中正数与负数个数相等的最长子数组长度。
将数组所有的正数都变为1,负数都变为-1,0不变,然后求累加和为0的最长子数组长度。
2.给定一个无序数组arr,其中元素只是1或0。求arr所有的子数组中0和1个数相等的最长子数组长度
将数组所有的0全部变成-1,1不变,然后求累加和为0的最长子数组长度。
public static int longestSubArrayInPosArrary(int[] arr, int aim){
if (arr == null || arr.length ==0 || aim <= 0) return 0;
int left = 0;
int right = 0;
int sum = arr[0];
int res = 0;
while (right < arr.length) {
if (sum == aim){
res = Math.max(res, right - left + 1);
right++;
if ( right == arr.length) break;
sum += arr[right];
}else if (sum < aim){
right ++;
if ( right == arr.length) break;
sum += arr[right];
}else {
sum -= arr[left];
left++;
}
}
return res;
}
两个指针,构成一个窗口,然后向右滑动
public static int longestSubArrayInPosArrary(int[] arr, int aim){
if (arr == null || arr.length ==0 || aim <= 0) return 0;
int left = 0;
int right = 0;
int sum = arr[0];
int res = 0;
while (right < arr.length) {
if (sum == aim){
res = Math.max(res, right - left + 1);
right++;
if ( right == arr.length) break;
sum += arr[right];
}else if (sum < aim){
right ++;
if ( right == arr.length) break;
sum += arr[right];
}else {
sum -= arr[left];
left++;
}
}
return res;
}
全是正数,两个指针,构成一个窗口,增加窗口和增加、缩短窗口和减少
计算从i到N-1上的最小的累加和,保存在一个数组中。
public static int maxLength(int [] arr, int aim){
if (arr == null || arr.length < 1) return 0;
int[] sums = new int[arr.length];
int[] indexs = new int[arr.length];
sums[arr.length - 1] = arr[arr.length - 1];
indexs[arr.length - 1] = arr.length - 1;
for (int i = arr.length - 2; i >= 0; i --){
if (sums[i + 1] < 0){
sums[i] = arr[i] + sums[i + 1];
indexs[i] = indexs[i + 1];
}else {
sums[i] = arr[i];
indexs[i] = i;
}
}
int R = 0;
int sum = 0;
int len = 0;
for (int start = 0; start < arr.length; start++){
while (R < arr.length && sum + sums[R] <= aim){
sum += sums[R];
R = indexs[R] + 1;
}
sum -= R > start ? arr[start] : 0;
len = Math.max(len,R - start);
R = Math.max(R,start + 1);
}
return len;
}
public static int mostEOR(int[] arr){
int ans = 0;
int xor = 0;
int[] dp = new int[arr.length];
HashMap<Integer,Integer> map = new HashMap<>();
map.put(0,-1);
for (int i = 0; i < arr.length; i++){
xor ^= arr[i];
System.out.print(xor+" ");
System.out.println(map);
if (map.containsKey(xor)){ //3,2,1,0,3,2,1,2,1
int pre = map.get(xor);
dp[i] = pre == -1 ? 1 : (dp[pre] + 1);
}
if (i > 0){
dp[i] = Math.max(dp[i-1],dp[i]);
}
map.put(xor,i);
ans = Math.max(ans,dp[i]);
}
return ans;
}
3 {0=-1}
1 {0=-1, 3=0}
0 {0=-1, 1=1, 3=0}
0 {0=2, 1=1, 3=0}
3 {0=3, 1=1, 3=0}
1 {0=3, 1=1, 3=4}
0 {0=3, 1=5, 3=4}
2 {0=6, 1=5, 3=4}
3 {0=6, 1=5, 2=7, 3=4}
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。