70 两数之和-小于或等于目标值（Two Sum - Less than or equal to target）

文章目录

• • 1 题目
  • 2 解决方案
  • • 2.1 思路
    • 2.2 时间复杂度
    • 2.3 空间复杂度
  • 3 源码

1 题目

题目：两数和-小于或等于目标值（Two Sum - Less than or equal to target）
描述：给定一个整数数组，找出这个数组中有多少对的和是小于或等于目标值。返回对数。

lintcode题号——609，难度——medium

样例1：

输入: nums = [2, 7, 11, 15], target = 24. 
输出: 5. 
解释:
2 + 7 < 24
2 + 11 < 24
2 + 15 < 24
7 + 11 < 24
7 + 15 < 24

样例2：

输入: nums = [1], target = 1. 
输出: 0. 

2 解决方案 2.1 思路

  使用对向双指针的方式，两个指针分别从头尾开始向中间走，若指针指向的两个值的和小于或等于目标值，则将右指针左移动的所有组合（必定小于或等于目标值）加入结果，然后左指针往右一步；若两个值的和大于目标值，则右指针往左一步，不断循环，直到找到结果。

2.2 时间复杂度

  时间复杂度为O(n)。

2.3 空间复杂度

  空间复杂度为O(1)。

3 源码

细节：

1. 使用对向双指针的方式。
2. 需要先进行排序。
3. 找到符合条件的结果后，要将后续右指针左移的所有符合条件的组合都加入结果，因为left+right<=target，则一定有left+(right左边的所有数)<=target。

C++版本：

/**
* @param nums: an array of integer
* @param target: an integer
* @return: an integer
*/
int twoSum5(vector &nums, int target) {
    // write your code here
    int result = 0;
    if (nums.size() < 2)
    {
        return result;
    }

    // 先对数组进行排序
    sort(nums.begin(), nums.end());

    int left = 0;
    int right = nums.size() - 1;
    while (left < right)
    {
        if (nums.at(left) + nums.at(right) <= target)
        {
            result = result + (right - left); // right向左移的所有结果都小于目标值
            left++;
        }
        else if (nums.at(left) + nums.at(right) > target)
        {
            right--;
        }
    }

    return result;
}