LeetCode（Binary Search)2389. Longest Subsequence With Limited Sum

àì夳堔傛蜴生んèń 2023-09-25 23:37 11阅读 0赞

# 1.问题 #

You are given an integer array nums of length n, and an integer array queries of length m.

Return an array answer of length m where answer\[i\] is the maximum size of a subsequence that you can take from nums such that the sum of its elements is less than or equal to queries\[i\].

A subsequence is an array that can be derived from another array by deleting some or no elements without changing the order of the remaining elements.

Example 1:

> Input: nums = \[4,5,2,1\], queries = \[3,10,21\]  
> Output: \[2,3,4\]  
> Explanation: We answer the queries as follows:
> 
>  *  The subsequence \[2,1\] has a sum less than or equal to 3. It can be proven that 2 is the maximum size of such a subsequence, so answer\[0\] = 2.
>  *  The subsequence \[4,5,1\] has a sum less than or equal to 10. It can be proven that 3 is the maximum size of such a subsequence, so answer\[1\] = 3.
>  *  The subsequence \[4,5,2,1\] has a sum less than or equal to 21. It can be proven that 4 is the maximum size of such a subsequence, so answer\[2\] = 4.

Example 2:

> Input: nums = \[2,3,4,5\], queries = \[1\]  
> Output: \[0\]  
> Explanation: The empty subsequence is the only subsequence that has a sum less than or equal to 1, so answer\[0\] = 0.

Constraints:

*  n == nums.length
 *  m == queries.length
 *  1 <= n, m <= 1000
 *  1 <= nums\[i\], queries\[i\] <= 106

# 2. 解题思路 #

## 方法1： ##

> 1.主要是通过对nums数组进行排序  
> 2.然后依次处理查询数组queries中的每个查询，对于每个查询值queries\[i\]，遍历排序后的nums数组，找到最小的j，使得nums\[0\]+nums\[1\]+…+nums\[j-1\]的和大于或等于查询值queries\[i\]  
> 3.并将结果存储在结果数组res中。
> 
>  *  具体来说，可以用`两个指针`来实现。
>  *  一个指针用于遍历nums数组，另一个指针用于记录当前的和。
>  *  在遍历nums数组时，如果当前的和加上nums\[j\]大于查询值queries\[i\]，则将结果数组res的当前位置设置为j，结束循环；
>  *  否则，将当前和加上nums\[j\]。如果已经遍历完nums数组，但是当前和仍然小于查询值queries\[i\]
>  *  则将结果数组res的当前位置设置为nums数组的长度。

## 方法2： ##

> 1.对 nums 数组进行排序；  
> 2.计算 nums 数组的前缀和，即将 nums 数组中每个元素依次累加，并存储在相应的位置上；  
> 3.对于每个查询值 q，使用二分查找在前缀和数组中找到第一个大于等于 q 的位置，即为答案。

## 方法3： ##

> 1.对数组 nums 进行排序，方便后面的操作。  
> 2.遍历查询数组 queries 中的每一个元素。  
> 3.对于当前的查询元素 queries\[i\]，定义一个变量 sum 用于记录当前的和，定义一个变量 count 用于记录当前和的个数，初始值均为 0。  
> 4.遍历数组 nums 中的每一个元素，如果当前的和加上当前的元素小于等于查询数组 queries 中的当前元素，则将当前的元素加入到和中，并将当前的元素个数加 1。  
> 5.将当前查询结果记录到结果数组中，继续下一个查询。  
> 6.返回查询结果数组。  
> 该算法的时间复杂度为 O(n \* m)，其中 n 和 m 分别为数组 nums 和查询数组 queries 的长度。该算法时间复杂度较高，可以通过二分查找等优化算法来提高效率。

# 3. 代码 #

## 代码1： ##

class Solution {
        
      public int[] answerQueries(int[] nums, int[] queries) {
        
            Arrays.sort(nums); // 对nums数组进行排序
            int[] res = new int[queries.length]; // 创建一个长度为queries.length的结果数组res
            for (int i = 0; i < queries.length; i++) {
         // 遍历查询数组queries
                int sum = 0, j = 0;
                for (j = 0; j < nums.length; j++) {
         // 遍历排序后的nums数组
                    if (sum + nums[j] > queries[i]) {
         // 如果当前的和加上nums[j]大于查询值queries[i]
                        res[i] = j; // 将结果数组res的当前位置设置为j
                        break; // 结束循环
                    }
                    sum = sum + nums[j]; // 否则，将当前和加上nums[j]
                }
                if (j == nums.length) res[i] = j; // 如果已经遍历完nums数组，则将结果数组res的当前位置设置为j
            }
            return res; // 返回结果数组res
    	}
    }

## 代码2： ##

class Solution {
        
      public int[] answerQueries(int[] nums, int[] queries) {
        
            Arrays.sort(nums);  // 对 nums 数组进行排序
            for(int i = 1; i < nums.length; i++) {
        
                nums[i] += nums[i - 1];  // 计算 nums 数组的前缀和
            }
    
            int[] ans = new int[queries.length];
            for(int i = 0; i < queries.length; i++) {
        
                int q = queries[i];
    
                // performing binary search for each query
                // 为每个查询值使用二分查找
                int low = 0, high = nums.length - 1;
                while(low <= high) {
        
                    int mid = low + (high - low) / 2;
                    if(nums[mid] == q) {
        
                        ans[i] = mid + 1;
                        break;
                    }
                    else if(nums[mid] < q) {
        
                        ans[i] = mid + 1;
                        low = mid + 1;
                    }
                    else {
        
                        high = mid - 1;
                    }
                }
            }
    
            return ans;
        
        }
    }

## 代码3： ##

class Solution {
        
        public static int[] answerQueries(int[] nums, int[] queries) {
        
            Arrays.sort(nums); // 对数组 nums 进行排序，方便后面的操作
            int[] result = new int[queries.length]; // 创建一个长度为 queries.length 的数组 result，用于存储查询结果
            for(int i=0;i<queries.length;i++){
         // 遍历查询数组 queries 中的每一个元素
                int sum=0; // 定义一个变量 sum 用于记录当前的和
                int count=0; // 定义一个变量 count 用于记录当前和的个数
                for (int j = 0; j < nums.length; j++) {
         // 遍历 nums 数组中的每一个元素
                    if(sum+nums[j]<=queries[i]){
         // 如果当前的和加上当前的元素小于等于查询数组 queries 中的当前元素
                        sum+=nums[j]; // 将当前的元素加入到和中
                        count++; // 将当前的元素个数加 1
                    }
                }
                result[i]=count; // 将当前查询结果记录到 result 数组中
            }
            return result; // 返回查询结果数组 result
        }
    }

> 思路基本相同，不同的地方在是根据nums遍历查找

class Solution {
        
        public int[] answerQueries(int[] nums, int[] queries) {
        
            Arrays.sort(nums); // 对数组 nums 进行排序，方便后面的操作
            int[] ans=new int[queries.length]; // 创建一个长度为 queries.length 的数组 ans，用于存储查询结果
            for(int i=0;i<queries.length;i++) // 遍历查询数组 queries 中的每一个元素
            {
        
                int sum=0; // 定义一个变量 sum 用于记录当前的和
                for(int j=0;j<nums.length;j++) // 遍历数组 nums 中的每一个元素
                {
        
                    sum+=nums[j]; // 将当前的元素加入到sum中
                    if(sum>queries[i]) // 如果当前的和大于查询数组 queries 中的当前元素
                    {
        
                        ans[i]=j; // 将当前元素的下标作为查询结果记录到 ans 数组中
                        break; // 跳出循环
                    }
                    if(j==nums.length-1 && sum<=queries[i]) // 如果遍历到了数组 nums 的最后一个元素，并且和仍然小于等于查询数组 queries 中的当前元素
                        ans[i]=j+1; // 将数组 nums 的长度作为查询结果记录到 ans 数组中
                }
            }
            return ans; // 返回查询结果数组 ans
        }
    }