描述

给定一个整数数组，找出这个数组中有多少对的和是小于或等于目标值。返回对数。

题目原地址

样例 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.  

算法

算法一 、暴力枚举

暴力 N2N2 枚举

算法二 、二分查找

算法思路

算法二在算法一的基础上进行改进

枚举一个数 nums[i]nums[i],找有多少个 j nums[i]+nums[j]<=targetnums[i]+nums[j]<=target 可以先对 numsnums 排序 然后使用二分查找的方式快速查找

复杂度分析

• 空间复杂度
• 三个算法都不需要多开辟空间，因此空间复杂度为 O(1)。
• 时间复杂度
• 算法一 暴力枚举 O(N2)O(N2)
• 算法二 枚举 ii，用二分查找加速 jj 的数量 时间复杂度 O(NlogN)O(NlogN)

代码：算法二

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 n = nums.size();          int ans = 0;         //对于每个 i，二分找到最大的 j nums[i]+nums[j]<=target         for(int i = 0; i < n - 1; i++) {             //确定二分上下界             int left = i;             int right = n;             int pos = i;             while(left + 1 < right) {                 int mid = left + (right - left) / 2;                 //不大于 target 可以提高下界                 if(nums[mid] + nums[i] <= target) {                     left = mid;                     pos = mid;                 }                 //缩小上界                 else {                     right = mid;                 }             }             //统计答案             ans += pos - i;         }         return ans;     } }  

可以在这里查看题目原地址

大佬有話說 (0)