LeetCode 1 Two Sum

    
        标签：
        
            数组类题目
        
            LeetCode
        
    发布于：2022-02-13 19:48:25
    编辑于：2022-02-13 20:07:00
    浏览量：674

概述

https://leetcode.com/problems/two-sum/

暴力法

时间复杂度 O(n^2)，空间复杂度 O(1) 。

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        for (int i = 0; i < nums.size(); i ++) {
            for (int j = i + 1; j < nums.size(); j ++) {
                if (nums[i] + nums[j] == target) return {i, j};
            }
        }
        return {0, 0};  // make complier happy
    }
};

双指针

时间复杂度 O(nlogn)，空间复杂度 O(n)。

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<pair<int, int>> p;
        for (int i = 0; i < nums.size(); i ++) {
            p.push_back({nums[i], i});
        }
        sort(p.begin(), p.end());
        for (int l = 0, r = nums.size() - 1; l < r;) {
            if (p[l].first + p[r].first == target) {
                return {p[l].second, p[r].second};
            } else if (p[l].first + p[r].first > target) {
                r --;
            } else {  // (p[l].first + p[r].first < target)
                l ++;
            }
        }
        return {0, 0};
    }
};

哈希表法

时间复杂度 O(n)，空间复杂度 O(n)。

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> m;
        for (int i = 0; i < nums.size(); i ++) {
            if (m.count(nums[i])) return {m[nums[i]], i};
            m[target - nums[i]] = i;
        }
        return {0, 0};
    }
};

Links: leetcode-1-two-sum