开发者社区> 李博 bluemind> 正文
阿里云
为了无法计算的价值
打开APP
阿里云APP内打开

[CareerCup] 17.12 Sum to Specific Value 和为特定数

简介:
+关注继续查看

17.12 Design an algorithm to find all pairs of integers within an array which sum to a specified value.

这道题实际上跟LeetCode上的Two Sum很类似,但是不同的是,那道题限定了只有一组解,而这道题说可以有很多组符合要求的解,那么我们先来看一种使用哈希表的解法,这种解法的时间复杂度是O(n),空间复杂度是O(1),思路是用哈希表建立每个数字和其下标之间的映射,遍历整个数字,如果target减去当前数字的值在哈希表中存在,那么返回这一对结果,然后更新当前数字在哈希表中的映射值,参见代码如下:

解法一:

void find_pairs(vector<int>& nums, int target) {
    unordered_map<int, int> m;
    for (int i = 0; i < nums.size(); ++i) {
        if (m.count(target - nums[i])) {
            cout << nums[i] << " " << nums[m[target - nums[i]]] << endl;
        }
        m[nums[i]] = i;
    }
}

下面这种方法是利用了双指针的思路,我们首先要把数组排个序,然后左右两个指针向中间移动,如果当前两个指针指的数加起来正好等于target,则找到了一对结果,如果大于target,那么我们将右指针左移一位,这样值能减小一些,如果和小于target,则把左指针右移一位,这样和能增大一些,参见代码如下:

解法二:

void find_pairs(vector<int> nums, int target) {
    sort(nums.begin(), nums.end());
    int left = 0, right = nums.size() - 1;
    while (left < right) {
        int sum = nums[left] + nums[right];
        if (sum == target) {
            cout << nums[left] << " " << nums[right] << endl;
            ++left; --right;
        } else if (sum > target) {
            --right;
        } else {
            ++left;
        }
    }    
}

本文转自博客园Grandyang的博客,原文链接:和为特定数[CareerCup] 17.12 Sum to Specific Value ,如需转载请自行联系原博主。

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

相关文章
《从零开始学Swift》学习笔记(Day48)——类型检查与转换
<span style="font-family:宋体;font-size: 10.5pt; mso-ascii-font-family: Arial; mso-fareast-font-family: 宋体; mso-fareast-theme-font: minor-fareast; mso-hansi-font-family: Arial; mso-bidi-font-family: A
1132 0
《从零开始学Swift》学习笔记(Day 12)——说几个特殊运算符
<div style="top: 0px;"></div> <span style="font-family:宋体;font-size:14px;"></span><p style="margin: 0cm 0cm 0pt; mso-outline-level: 1;"><span lang="EN-US" style="font-family:'Arial',sans-serif;fon
1016 0
+关注
李博 bluemind
云栖社区Java、Redis、MongoDB运营小编,有意合作请联系钉钉:15810436147
2107
文章
1103
问答
文章排行榜
最热
最新
相关电子书
更多
低代码开发师(初级)实战教程
立即下载
阿里巴巴DevOps 最佳实践手册
立即下载
冬季实战营第三期:MySQL数据库进阶实战
立即下载