Leetcode hot topic Hot 100 - > 1. Sum of two numbers

Description of the stem ：

Given an array of integers nums And an integer target value target, Please find... In the array and   For the target target the Two Integers , And return their The array subscript .

You can assume Each input will only correspond to one answer . however , Array The same element cannot be repeated in the answer .

You can press In any order Return to the answer .

LeetCode Original link https://leetcode.cn/problems/two-sum/

Catalog

Method 1： Violence enumeration

Method 1 analysis ：

Complexity analysis ：

Method 2： Sequencing

Method 2 analysis ：

Complexity analysis ：

Method 3： Hashtable

Method 3 analysis ：

Complexity analysis ：

---

Method 1： Violence enumeration

Method 1 analysis ：

Just pay attention to The second cycle From the Next position Start traversing , Because Avoid repeating the same subscript .

  The code is as follows ：

class Solution {
public:
	vector<int> twoSum(vector<int>& nums, int target) {
		vector<int>ans(2);
		for (int i = 0; i < nums.size(); i++)
		{
			for (int j = i + 1; j < nums.size(); j++) // Because the same element cannot be repeated , So from i+1 Start 
			{
				if (nums[i] + nums[j] == target)
				{
					ans[0] = i;
					ans[1] = j;
				}
			}
		}
		return ans;
	}
};

Complexity analysis ：

Time complexity ：O（）, among   Is the number of elements in the array , In the worst case, any two numbers in the array must be matched once .

Spatial complexity ：O（）, Only constant spaces are opened .

---

Method 2： Sequencing

Method 2 analysis ：

Because it is to find the sum of two numbers , So it's easy to think of Sort After use Double pointer To find , The problem is that the topic requires Returns the subscript , If you sort the original array directly , Then the original subscript cannot be found , So we choose to open up a new Temporary array , And then New array in lookup , After finding two evaluated values , Again Search the original array for subscripts . There is also a problem , Namely Original array There may be Elements of repetition The situation of , So two subscripts must be one Search from front to back , the other one Search back and forth , This avoids finding the same subscript .

The code is as follows ：

class Solution {
public:
	int FindPosFront(vector<int>& v, int val) // Look back before 
	{
		for (int i = 0; i < v.size(); i++)
		{
			if (v[i] == val)
			{
				return i;
			}
		}
		return -1;
	}
	int FindPosBack(vector<int>& v, int val) // Look backwards 
	{
		for (int i = v.size() - 1; i >= 0; i--)
		{
			if (v[i] == val)
			{
				return i;
			}
		}
		return -1;
	}
	vector<int> twoSum(vector<int>& nums, int target) {
		vector<int> ans(2);
		vector<int> tmp(nums);
		sort(tmp.begin(), tmp.end());
		int begin = 0;
		int end = nums.size() - 1;
		while (begin < end)
		{
			if (tmp[begin] + tmp[end] < target)
			{
				begin++;
			}
			else if (tmp[begin] + tmp[end] > target)
			{
				end--;
			}
			else
			{
				ans[0] = FindPosFront(nums, tmp[begin]);
				ans[1] = FindPosBack(nums, tmp[end]);
				break;
			}
		}
		return ans;
	}
};

Complexity analysis ：

Time complexity ：O（）, among   Is the number of elements in the array , The time complexity of quicksort is zero O（）, The complexity of other cycle times is O（）, Therefore, take the time complexity of quick sorting .

Spatial complexity ：O（）, Opened up a N A temporary array of sizes .

---

Method 3： Hashtable

Method 3 analysis ：

We found that the reason for the high time complexity of method 1 is to find target - x The time complexity of is too high . therefore , It's easy for us to think of establishing Hash map , In this way, you can find target - x The time complexity is reduced to O（N） Down to O（1）.

So we create a hash table , For each of these x, Let's first query the hash table Whether there is target - x, then take x Insert into hash table , Subsequent traversal to target-x when , Can then As previously inserted x Pairing , In this way Promise not to let x Match yourself .

The code is as follows ：

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> hashtable;
        vector<int> ans(2);
        for (int i = 0; i < nums.size(); ++i) 
        {
            auto it = hashtable.find(target - nums[i]); // Find out whether the corresponding element is in the hash table 
            if (it != hashtable.end()) // The corresponding element directly returns the result in the hash table 
            {
                ans[0] = it->second;
                ans[1] = i;
            }
            else // If not, add this element , Wait until the loop traverses the corresponding element , You can find this element 
            {
                hashtable[nums[i]] = i;
            }
        }
        return ans;
    }
};

Complexity analysis ：

Time complexity ：O(), among   Is the number of elements in the array . Only traversed the array once .

Spatial complexity ：O(), among   Is the number of elements in the array , Opened up a O() Size hash table .

---

That's all for sharing , I'm not very talented , There must be mistakes or thoughtlessness , If there are corrections or suggestions , Welcome to leave a message in the comment area , I will reply immediately after seeing it and make appropriate changes to the article after thinking , Thank you for reading ~