1498. Number of Subsequences That Satisfy the Given Sum Condition

Link

Solution

1. Sort Array

2. 找出區間其中min + max <= target，那麼其中的組合數是 2^(left - right)，因為min必定要在區間中。

ex. [1, 3, 6, 9] , target = 8

right = 0 , left = 2 時可以

[1], [1,3], [1, 6], [1,3,6] = 組合數是4 = 2^2

以此推進right or 減少left，找出所有可能數

​ 3. 另一個重點是pow的計算，因為會有overflow的關係，用pow[]來計算每個值，並在存入時mod 1e9 + 7

  public int numSubseq(int[] nums, int target) {
        Arrays.sort(nums);
        int left = nums.length -1;
        int right = 0;
        int ret = 0;
        int mod = (int)1e9 + 7;
        
        //計算pow的方法，避免overflow，當 len >= 64時連 double都罩不住
        int[] pows = new int[nums.length];
        pows[0] = 1;
        for (int i = 1 ; i < nums.length ; ++i)
            pows[i] = pows[i - 1] * 2 % mod;
        
        
        while(right <= left){
            if(nums[right] + nums[left] <= target){
                ret = (int)((pows[left-right] + ret) % mod);
                right++;
            }
            else{
                left--;
            }
        }
        return ret;
        
    }