题解59 | 哈希表!斯哈斯哈!#和为S的两个数字#

class Solution {
  public:
    vector<int> FindNumbersWithSum(vector<int> array, int sum) {
        vector<int> ans;

        // for (int i = 0; i < array.size(); i++) {
        //     int flag = 0;
        //     int target = sum - array[i];
        //     ans.push_back(array[i]);
        //     for (int j = 0; j < array.size(); j++) {
        //         if(j == i) continue;
        //         if (array[j] == target) {
        //             ans.push_back(array[j]);
        //             flag = 1;
        //             return ans;
        //         }
        //     }
        //     if (flag == 0) {
        //         ans.pop_back();
        //     }
        // }最后一组超时了
	//这段代码的基本思想是遍历数组，对于每个元素array[i]，计算目标值target = sum - array[i]，然后再次遍历		//数组查找是否存在target。如果找到了，则将array[i]和target添加到结果数组ans中并返回。
	//时间复杂度：O(n^2)，其中n为数组的长度。外层循环需要遍历n次，内层循环也需要遍历n次，因此总的时间复杂度为O(n^2)。
	//空间复杂度：O(1)，只需要使用常数个额外变量来保存结果，没有使用额外的空间。

        //创建哈希表---值、下标
        unordered_map<int, int> mp;
        //在哈希表中查找sum-array[i]
        for (int i = 0; i < array.size(); i++) {
            int target = sum - array[i];
            if (mp.find(target) == mp.end()) {//找不到标零
                mp[array[i]] = 0;
            } 
            else {//找到了推进结果数组返回即可
                ans.push_back(array[i]);
                ans.push_back(target);
                return ans;
            }
           
        }
        return ans;//如果无法找出这样的数字，返回一个空数组即可。
    }
};

基本算法思想：

1. 使用哈希表存储数组中的元素和对应的下标。

2. 遍历数组，对于每个元素array[i]，计算目标值target = sum - array[i]。

3. 在哈希表中查找target，如果找到了，则将array[i]和target添加到结果数组ans中并返回。

4. 如果遍历完数组仍然没有找到满足条件的数字对，则返回一个空数组。

时间复杂度：

O(n)，其中n为数组的长度。遍历数组需要O(n)的时间，哈希表的插入和查找操作的时间复杂度为O(1)。

空间复杂度：

O(n)，需要使用一个哈希表来存储数组中的元素。