未排序数组中累加和为给定值的最长子数组长度

Neo
Neo
2020-09-22 / 0 评论 / 275 阅读

题目描述

给定一个无序数组arr, 其中元素可正、可负、可0。给定一个整数k,求arr所有子数组中累加和为k的最长子数组长度

输入描述:

第一行两个整数N, k。N表示数组长度,k的定义已在题目描述中给出
第二行N个整数表示数组内的数

输出描述:

输出一个整数表示答案

示例1

输入
5 0
1 -2 1 1 1

输出
3

解题

解题思路:
这道题目最开始的时候我觉得还是比较简单,直接用两个循环遍历所有子数组,同时更新len。但是测试的时候发现case通过率只有70%,然后超时了,果然,没有免费的午餐!

然后看了其它人巧妙方法:
用一个单循环去遍历数组,遍历的同时将累加和依次保存在hashmap中,key表示依次的累加和,value表示累加和对应的下标。核心思想如下:
令i表示子数组的左下标,令j表示子数组的右下标,令$s_j$表示从$0-j$的累加和,$s_i$表示$0-i$的累加和,那么$s_j-s_
$表示从$i-j$子数组的累加和。这些累加和及其下标都保存在hashmap中,每遍历一个元素进行一次检测即可。

import java.io.*;
import java.util.*;

public class Main{
    
    public static void main(String[] args) throws IOException{
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        String[] str = in.readLine().split(" ");
        int n = Integer.parseInt(str[0]);
        int k = Integer.parseInt(str[1]);
        int[] arr = new int[n];
        int j = 0;
        for(String i:in.readLine().split(" ")){
            arr[j++] = Integer.parseInt(i);
        }
        System.out.println(getLength2(arr,k));
        
    }

    //case通过率70%,然后超时
    static int getLength(int[] arr,int k){
        int len = 0;
        int sum = 0;
        for(int left=0;left<arr.length;left++){
            sum = 0;
            for(int right=left;right<arr.length;right++){
                sum += arr[right];
                if(sum == k){
                    len = Math.max(len,right-left+1);
                }
            }
        }
        return len;
    }
    
    static int getLength2(int[] arr,int k){
        int len = 0;
        int sum = 0;
        HashMap<Integer,Integer> map = new HashMap<>();
        map.put(0,-1);
        for(int i=0;i<arr.length;i++){
            sum += arr[i];
	    //将新的累加和添加到map中,重复的就不需要了,map中只保存最早的累加和
            if(!map.containsKey(sum))
                map.put(sum,i);
	    //检测是否有满足k值的子数组
            if(map.containsKey(sum-k))
                len = Math.max(i - map.get(sum-k),len);
        }
        
        return len;
    }
}

拓展问题

拓展问题1
给定一个无序数组arr,其中元素可正、可负、可0。求arr所有子数组中正数与负数个数相等的最长子数组的长度。
[要求]
时间复杂度为O(n),空间复杂度为O(n)
解题思路
题目要求的是正数和负数相等,如果我们将正数修改为1、负数修改为-1,那么当子数组的和为0时,该题也就转化成上面的原题形式。

拓展问题2
给定一个无序数组arr,其中元素只能是1或0。求arr所有的子数组中0和1个数相等的最长子数组的长度
[要求]
时间复杂度为O(n),空间复杂度为O(n)
解题思路
将数组中所有的0修改成-1,该题同样可以变成原题形式。