Leetcode学习-四十二天

阿里云国内75折回扣微信号：monov8

阿里云国际，腾讯云国际，低至75折。AWS 93折免费开户实名账号代冲值优惠多多微信号：monov8 飞机：@monov6

第四十二天

我使用的C++错误的地方请见谅文章初衷仅用来督促本人学习如果恰巧能够给你带来帮助我会十分开心。

文章目录

第四十二天
一、两个数组的交集 II
二、两数之和 II - 输入有序数组

一、两个数组的交集 II

给你两个整数数组 nums1 和 nums2 请你以数组形式返回两数组的交集。返回结果中每个元素出现的次数应与元素在两个数组中都出现的次数一致如果出现次数不一致则考虑取较小值。可以不考虑输出结果的顺序。

示例 1

输入nums1 = [1,2,2,1], nums2 = [2,2]
输出[2,2]
示例 2:

输入nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出[4,9]

作者力扣 (LeetCode)
链接https://leetcode.cn/leetbook/read/binary-search/xe3pwj/
来源力扣LeetCode
著作权归作者所有。商业转载请联系作者获得授权非商业转载请注明出处。

class Solution {
public:
    vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
        sort (nums1.begin(), nums1.end());
        sort (nums2.begin(), nums2.end());
        int n1 = nums1.size(), n2 = nums2.size();
        int idx1 = 0, idx2 = 0;
        vector<int> ans;
        while (idx1 < n1 && idx2 < n2) {
            if (nums1[idx1] < nums2[idx2]) {
                idx1++;
            } else if (nums1[idx1] > nums2[idx2]) {
                idx2++;
            } else {
                ans.push_back(nums1[idx1]);//相同元素置入相比上一道题目反而少了判断的一步
                idx1++;
                idx2++;
            }
        }
        return ans;
    }
};

二、两数之和 II - 输入有序数组

给你一个下标从 1 开始的整数数组 numbers 该数组已按非递减顺序排列请你从数组中找出满足相加之和等于目标数 target 的两个数。如果设这两个数分别是 numbers[index1] 和 numbers[index2] 则 1 <= index1 < index2 <= numbers.length 。

以长度为 2 的整数数组 [index1, index2] 的形式返回这两个整数的下标 index1 和 index2。

你可以假设每个输入只对应唯一的答案而且你不可以重复使用相同的元素。

你所设计的解决方案必须只使用常量级的额外空间。

示例 1

输入numbers = [2,7,11,15], target = 9
输出[1,2]
解释2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。返回 [1, 2] 。

作者力扣 (LeetCode)
链接https://leetcode.cn/leetbook/read/binary-search/xeqevt/
来源力扣LeetCode
著作权归作者所有。商业转载请联系作者获得授权非商业转载请注明出处。

class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) {
        //利用双指针一个在数组头一个在数组尾如果和比target小则左指针右移如果大于target则右指针左移且绝不会漏掉正确答案
        int l = 0, r = numbers.size() - 1;
        //vector<int> ans;
        
        while (l < r) {
            int sum = numbers[l] + numbers[r];
            if (sum == target) {
                
                return {l + 1, r + 1};
            } else if (sum < target) {
                l++;
            } else {
                r--;
            }
        }
        return {-1, -1};
    }
};