阿里面试真题详解:两数和-小于或等于目标值-阿里云开发者社区

开发者社区> 算法编程> 正文
登录阅读全文

阿里面试真题详解:两数和-小于或等于目标值

简介: 阿里面试真题详解:两数和-小于或等于目标值

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

在线评测地址:领扣题解官网

样例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排序 然后使用二分查找的方式快速查找
算法三 双指针
利用双指针 start,endstart,end求解
对于每个startstart,找到最大的endend,使得A[start]+B[end]A[start]+B[end]小于等于x
这样,因为数组是单调的,所以 A[start]+B[end+1]....A[start]+B[n−1]A[start]+B[end+1]....A[start]+B[n−1] 都大于xx
所以对于startstart,一共有end+1end+1对a+ba+b的和小于等于xx.
startstart移动到下一个位置,再去求新的endend
因为数组元素都是单调的,所以若A[start]+B[j]A[start]+B[j]大于xx,则A[start+1]+B[j]A[start+1]+B[j]一定也大于xx,所以,在startstart 移动到下一个位置时候,我们不需要重新从开始位置求一遍endend,而是在上一次求得endlastendlast基础上继续减少就可以了。
证明如下:
A[oldstart]+B[oldend]≤xA[oldstart]+B[oldend]≤x
oldstart<newstartoldstart<newstart
所以A[oldstart]+B[oldend+1]>xA[oldstart]+B[oldend+1]>x
推出A[newstart]+B[oldend+1]>xA[newstart]+B[oldend+1]>x
所以newend≤oldendnewend≤oldend

复杂度分析

  • 空间复杂度
  • 三个算法都不需要多开辟空间,因此空间复杂度为O(1)。
  • 时间复杂度
  • 算法一 暴力枚举O(N2)O(N2)
  • 算法二 枚举ii,用二分查找加速jj的数量 时间复杂度O(NlogN)O(NlogN)
  • 算法三 双指针,start最多增加n次 end最多减少n次 所以时间复杂度O(N)O(N)
    代码:算法二

    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;
    }
    }
    代码:算法三
    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 start = 0, end = n - 1;
        //答案
        int ans = 0;
        while(start <= n - 1) {
            //找到最小的end nums[start]+nums[end]<=target
            while(end >= 0) {
                if(nums[start] + nums[end] > target) {
                    end -= 1;
                } else {
                    break;
                }
            }
            //只记录start<end的情况
            if(end > start) {
                ans += end - start;
            } else {
                break;
            }
            start += 1;
        }
        return ans;
    }
    }

更多题解参考:九章官网solution

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

分享:
算法编程
使用钉钉扫一扫加入圈子
+ 订阅

开发者社区在线编程频道官方技术圈。包含算法资源更新,周赛动态,每日一题互动。

官方博客
链接