Description

• Notes
• Testcase
• Judge

Given an array of integers, find how many pairs in the array such that their sum isless than or equal toa specific target number. Please return the number of pairs.

Have you met this question in a real interview?

Yes

Example

Given nums =[2, 7, 11, 15], target =24.
Return5.
2 + 7 < 24
2 + 11 < 24
2 + 15 < 24
7 + 11 < 24
7 + 15 < 25

Tags

Sort

Two Pointers

class Solution {
public:
/\*\*

 \* @param nums an array of integer

 \* @param target an integer

 \* @return an integer

 \*/

int twoSum5(vector<int> &nums, int target) {

    // Write your code here

    sort(nums.begin(), nums.end());

    int left = 0, right = nums.size() - 1;

    int pairs = 0;

    while (left < right) {
        if (nums[left] + nums[right] <= target) {
            pairs += (right - left);
            ++left;
        }  else {
            --right;
        }
    }

    return pairs;

}