# 1918. Kth Smallest Subarray Sum
###### tags: `Leetcode` `Medium` `Binary Search` `Sliding Window`
Link: https://leetcode.com/problems/kth-smallest-subarray-sum/
## 思路 $O(NlogN)$ $O(1)$
binary search on kthSmallestSubarraySum
猜测所有可能的subarray sum，然后看比它小的subarray有多少
用sliding window计算比它小的subarray有多少
## Code

class Solution {
    public int kthSmallestSubarraySum(int[] nums, int k) {
        int sum = 0;
        for(int num:nums) sum += num;
        int start=0, end=sum;
        while(start<end){
            int mid = start+(end-start)/2;
            if(k>numberOfSubarraySumLessThanX(nums, mid)){
                start = mid+1;
            }
            else{
                end = mid;
            }
        }
        return start;
    }
    private int numberOfSubarraySumLessThanX(int[] nums, int x){
        int num = 0;
        int curr = 0;
        int l=0, r=0;
        while(r<nums.length){
            curr += nums[r];
            while(curr>x){
                curr-=nums[l++];
            }
            num += r-l+1;
            r++;
        }
        return num;
    }
}