[Java/C++/Python] Two Sum
Intuition\nAlmost same as problem two sum.\nIf we want to know the count of subarray in sorted array A,\nthen it\'s exactly the same.\nMake sure you can do two 
# **Intuition**\nAlmost same as problem two sum.\nIf we want to know the count of subarray in sorted array `A`,\nthen it\'s exactly the same.\nMake sure you can do two sum before continue.\n<br>\n\n# **Explanation**\nSort input `A` first,\nFor each `A[i]`, find out the maximum `A[j]`\nthat `A[i] + A[j] <= target`.\n\nFor each elements in the subarray `A[i+1] ~ A[j]`,\nwe can pick or not pick,\nso there are `2 ^ (j - i)` subsequences in total.\nSo we can update `res = (res + 2 ^ (j - i)) % mod`.\n\nWe don\'t care the original elements order,\nwe only want to know the count of sub sequence.\nSo we can sort the original `A`, and the result won\'t change.\n<br>\n\n# **Complexity**\nTime `O(NlogN)`\nSpace `O(1)` for python\n(`O(N)` space for java and c++ can be save anyway)\n<br>\n\n**Java**\n```java\n    public int numSubseq(int[] A, int target) {\n        Arrays.sort(A);\n        int res = 0, n = A.length, l = 0, r = n - 1, mod = (int)1e9 + 7;\n        int[] pows = new int[n];\n        pows[0] = 1;\n        for (int i = 1 ; i < n ; ++i)\n            pows[i] = pows[i - 1] * 2 % mod;\n        while (l <= r) {\n            if (A[l] + A[r] > target) {\n                r--;\n            } else {\n                res = (res + pows[r - l++]) % mod;\n            }\n        }\n        return res;\n    }\n```\n**C++**\n```cpp\n    int numSubseq(vector<int>& A, int target) {\n        sort(A.begin(), A.end());\n        int res = 0, n = A.size(), l = 0, r = n - 1, mod = 1e9 + 7;\n        vector<int> pows(n, 1);\n        for (int i = 1 ; i < n ; ++i)\n            pows[i] = pows[i - 1] * 2 % mod;\n        while (l <= r) {\n            if (A[l] + A[r] > target) {\n                r--;\n            } else {\n                res = (res + pows[r - l++]) % mod;\n            }\n        }\n        return res;\n    }\n```\n**Python:**\n```py\n    def numSubseq(self, A, target):\n        A.sort()\n        l, r = 0, len(A) - 1\n        res = 0\n        mod = 10**9 + 7\n        while l <= r:\n            if A[l] + A[r] > target:\n                r -= 1\n            else:\n                res += pow(2, r - l, mod)\n                l += 1\n        return res % mod\n```\n<br>\n
[]