Java solution, Sum of Sliding window


  • 24
    public class Solution {
        public double findMaxAverage(int[] nums, int k) {
            long sum = 0;
            for (int i = 0; i < k; i++) sum += nums[i];
            long max = sum;
            
            for (int i = k; i < nums.length; i++) {
                sum += nums[i] - nums[i - k];
                max = Math.max(max, sum);
            }
            
            return max / 1.0 / k;
        }
    }
    

  • 0
    L

    Can't this be done using a Hash table? I was thinking something on the lines of Subarray sum equals k, just that instead of sum we need average and that the length should be k.


  • 0
    N

    nice solution


  • 6

    no need to use long ....


  • 1
    H

    This is my Java solution.

    public class Solution {
        public double findMaxAverage(int[] nums, int k) {
            int curr = 0;
            int max = Integer.MIN_VALUE;
    
            for(int i = 0; i < nums.length; i++){
            	curr += nums[i];
            	if(i - k  >=0) curr -= nums[i-k];
            	if(i >= k-1 )max = Math.max(curr,max);
            }
            return (double)max/k;
        }
    
    }
    
    

  • 0
    F

    Similar idea

    public class Solution {
        public double findMaxAverage(int[] nums, int k) {
            int sum = 0;
            for(int i = 0;i<k;i++){
                sum += nums[i];
            }
            int maxAvg = sum;
            int index = 0;
            for(int i = k;i<nums.length;i++){
                sum -= nums[index++];
                sum += nums[i];
                maxAvg = Math.max(maxAvg, sum);
            }
            return (double)maxAvg / k;
        }
    }
    

  • 2

    share my solution, without pre computing the first sliding window

    public class Solution {
        public double findMaxAverage(int[] nums, int k) {
            int size = nums.length;
            int max = Integer.MIN_VALUE;
            int sum = 0;
    
            for (int i = 0 ; i < size; i++) {
                //subtract
                if (i > k - 1) {
                    sum -= nums[i - k];
                }
    
                //add
                sum += nums[i];
    
                //update max
                if (i >= k - 1) {
                    if (sum > max) {
                        max = sum;
                    }
                }
            }
    
            return (max + 0.0)/k;
        }
    }
    

  • 0
    J

    @Hellokitty_2015
    I think the first comment "abstract" is subtract, right?


  • 0

    @jshi11 Thanks for pointing it out, you are right. It should be subtract.


  • 1
    Q

    @Hellokitty_2015
    for //update max. if you use if (sum > max), Math.max is no longer necessary.


  • 0
        public double findMaxAverage(int[] nums, int k) {
          int sum = 0;  
          for(int i = 0; i < k; i++){
            sum += nums[i];  
          } 
          int max = sum;  
          for(int i = k; i < nums.length; i++){
            sum -= nums[i - k];
            sum += nums[i]; 
            max = Math.max(max, sum);  
          }
          return (double) max / (double) k;  
        }

  • 0

    @qinzhou you're right. Thanks a lot!!


  • 0
    G

    So short and concise, why this solution is not the highest voted one?


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.