LeetCode Solution-1

蔚落 2023-08-17 17:45 129阅读 0赞

1.  Two Sum  
    Given an array of integers, return indices of the two numbers such that they add up to a specific target.  
    You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example:  
Given nums = \[2, 7, 11, 15\], target = 9, Because nums\[0\] + nums\[1\] = 2 + 7 = 9, return \[0, 1\].

思路1：利用哈希表。

1.  首先新建一个哈希表(unordered\_map)，存储输入数组元素及对应的下标。
2.  对数组元素进行遍历，对每个值得到其和目标值的差值(dif)，在数组中寻找dif，如果存在且下标不重复即得到结果，若遍历后无结果则返回空数组。

Solution：

vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> num_id;
        for (int i = 0; i < nums.size(); i++) {
            num_id[nums[i]] = i;
        }
    
        for (int i = 0; i < nums.size(); i++) {
            int dif = target - nums[i];
            auto dif_id = num_id.find(dif);
            if (dif_id != num_id.end() && dif_id->second != i) 
                return vector<int>{i, dif_id->second};
        }
        return vector<int>();
    }

性能：  
Runtime: 8 ms  Memory Usage: 10.5 MB

思路2：对数组排序

1.  先保存原数组为num，然后对原数组按从小到大进行排序；
2.  设定2个值begin和end分别作为开始和结束值的下标；
3.  比较nums\[beign\]和nums\[end\]的和sum与target的大小，若sum < target，则说明2数偏小，begin++；若sum > target，则说明两数之和偏大，end--；如果sum = target，则进入4；
4.  在num中分别查找nums\[begin\]和nums\[end\]对应的下标值，并判断2数是否相等，若不相等即是最后的输出。

Solution:

vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> num, res;
        int n = nums.size();
        num = nums;
        sort(nums.begin(), nums.end());
        
        int begin = 0, end = n - 1;
        while (begin < end) {
            int sum = nums[begin] + nums[end];
            if (sum < target) begin++;
            else if (sum > target) end--;
            else
            {
                for (int i = 0; i < n; i++) {
                    if (num[i] == nums[begin]) {
                        res.push_back(i);
                        break;
                    }
                }
                for (int i = 0; i < n; i++) {
                    if (num[i] == nums[end] && i != res[0]) {
                        res.push_back(i);
                        break;
                    } 
                }
                
                return res;
            }
        }
        return res;
    }

性能：  
Runtime: 8 ms  Memory Usage: 9.5 MB

转载于:https://www.cnblogs.com/dysjtu1995/p/11477017.html