2389. Longest Subsequence With Limited Sum

문제

https://leetcode.com/problems/longest-subsequence-with-limited-sum/description/

풀이

class Solution {
    public int[] answerQueries(int[] nums, int[] queries) {
        int n = nums.length;
        int m = queries.length;
        int[] answer = new int[m];
        Arrays.sort(nums);

        for(int i = 1; i < n; i++) {
            nums[i] += nums[i-1];
        }

        for(int i = 0; i < m; i++) {
            int target = queries[i];
            int lt = 0;
            int rt = n - 1;
            int mid = (lt + rt) / 2;
            while(lt <= rt) {
                if(nums[mid] < target) {
                    lt = mid + 1;
                    answer[i] = mid + 1;
                }
                if(nums[mid] > target) {
                    rt = mid - 1;
                }
                if(nums[mid] == target) {
                    answer[i] = mid + 1;
                    break;
                }
                mid = (lt + rt)/2;
            }
        }
        return answer;
    }
}

• prefix sum + binary search