AcWing 75. 和为S的两个数字
宋标 Lv5
  2022-08-18 02:30:51 2022-08-18 02:30    

题目

输入一个数组和一个数字 ，在数组中查找两个数，使得它们的和正好是 。

如果有多对数字的和等于 ，输出任意一对即可。

你可以认为每组输入中都至少含有一组满足条件的输出。

数据范围

数组长度 。

样例

输入：[1,2,3,4] , sum=7

输出：[3,4]

题解

时间复杂度O(N*logN), 空间复杂度O(1)的做法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public:

    void q_sort(vector<int>& nums, int l, int r)
    {
        if (l >= r) return;
        int i = l - 1, j = r + 1, mid = l + r >> 1;
        while (i < j)
        {
            while (nums[++ i] < nums[mid]);
            while (nums[-- j] > nums[mid]);
            if (i < j) swap(nums[i], nums[j]);
        }
        q_sort(nums, l, j); q_sort(nums, j + 1, r);
    }

    vector<int> findNumbersWithSum(vector<int>& nums, int target) {
        q_sort(nums, 0, nums.size() - 1);

        for (int i = 0, j = nums.size() - 1; i < j; ++ i)
        {
            if (nums[i] + nums[j] == target) return vector<int>{nums[i], nums[j]};
            while (nums[i] + nums[j] > target) -- j;
        }

        return vector<int>();
    }
};

时间复杂度O(N), 空间复杂度O(N)的做法

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    vector<int> findNumbersWithSum(vector<int>& nums, int target) {
        unordered_set<int> hash;
        for (int i = 0; i < nums.size(); ++ i)
        {
            if (hash.count(target - nums[i])) return vector<int>{target - nums[i], nums[i]};
            hash.insert(nums[i]);
        }
        return vector<int>();
    }
};
 评论