[LeetCode] 1498. Number of Subsequences That Satisfy the Given Sum Condition

https://leetcode.com/problems/number-of-subsequences-that-satisfy-the-given-sum-condition/

Number of Subsequences That Satisfy the Given Sum Condition - LeetCode

문제 유형 : 투 포인터

문제 난이도 : Medium

 

문제

You are given an array of integers nums and an integer target.

Return the number of non-empty subsequences of nums such that the sum of the minimum and maximum element on it is less or equal to target. Since the answer may be too large, return it modulo 10^9 + 7.

 

정수 배열과 정수 target값이 주어진다. 빈칸이 없는 subsequence의 수를 반환하라. 

subsequence의 조건 : 최소값과 최대값의 합이 target보다 작거나 같아야함.

답이 너무 커질 수도있으니, 10^9+7로 나누어라.

 

 

문제 해결

우선 받은 배열을 정렬한다.

그 뒤, 투 포인터를 이용하면 된다.

subsequence의 수는 부분집합의 수를 구하듯이 해주면 된다.

조건에 맞는 가장 큰 right를 만들어주고,

2^(right - left)를 누적시킨다.

그 뒤, left 포인터를 늘리고, 반복해주면 된다.

 

코드(C++)

class Solution {
public:
    int numSubseq(vector<int>& nums, int target) {
        int n = nums.size();
        int mod = 1e9 + 7;
        long answer = 0;
        sort(nums.begin(), nums.end());
        
        vector<int> pow2(n, 1);
        
        for (int i = 1; i < n; i++) {
            pow2[i] = (pow2[i - 1] * 2) % mod;
        }
        
        int left = 0;
        int right = n - 1;
        
        while (left <= right) {
            if (nums[left] + nums[right] > target) {
                right--;
            } else {
                answer = (answer + pow2[right - left]) % mod;
                left++;
            }
        }
        return answer;
    }
};