<hashmap><双指针>最长子数组长度问题
原创
一、无序数组累加和为k的最长子数组长度
给定一个无序数组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的最长子数组长度。
三、全是正数的数组累加和为k的最长子数组长度
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;
}两个指针，构成一个窗口，然后向右滑动
四、全是正数的数组累加和为k的最长子数组长度
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;
}全是正数，两个指针，构成一个窗口，增加窗口和增加、缩短窗口和减少
五、可正可负可0的数组中，累加和小于等于k的子数组的最大的长度是多少？
计算从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;
}六、数组异或和为0的子数组最多是多少
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 删除。
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
