C + + & Python description LeetCode 1 Sum of two numbers

   Hello, I'm q í gu ā n ji e, sharing some technical posts in the official account, CSDN, GitHub, B station, HUAWEI Developer Forum and so on. It's not hard to give up, but persistence must be cool! Time flies, the future can be expected, come on~

If you love bloggers' articles, you can focus on the official account of the blogger (Q gu). ā n ji E) if you need to find a blogger, you can leave a message at the back of the official account. Built a small communication group, Q group: 545611263. If you want to enter the wechat group, you can add my V:qiguanjie2015 remarks to pull the group.

                              81. Buddy official account is updated regularly every day at WeChat official account. Depending on the circumstances, other partners who are interested in brushing the problem together can pay attention to the public numbers to roll together.

subject

Given an integer array nums and an integer target value target, please find the two integers with and as the target value target in the array and return their array subscripts.

You can assume that each input will correspond to only one answer. However, the same element in the array cannot appear repeatedly in the answer.

You can return answers in any order.

Example 1:

Input: nums = [2,7,11,15], target = 9
 Output:[0,1]
Explanation: because nums[0] + nums[1] == 9 ，return [0, 1] . 

Example 2:

Input: nums = [3,2,4], target = 6
 Output:[1,2]

Example 3:

Input: nums = [3,3], target = 6
 Output:[0,1]

Tips:

• 2 <= nums.length <= 104
• -109 <= nums[i] <= 109
• -109 <= target <= 109
• There will only be one valid answer

**Advanced: * * can you think of an algorithm with less time complexity than O(n2)?

Solution I violence

Since given an array, let's find any combination with target as the target value, then our simplest and most violent way is to loop through two layers to see if there are such two numbers. If there are, return these two numbers. If there is no such number, return []. In order to avoid the two digits being the same, we need to pay attention to the double loop, We can iterate through the subscript of the second cycle from the subscript of the first cycle + 1K

Solution I C + + implementation

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

Solution - python implementation

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        for i,num_i in enumerate(nums):
            for j,num_j in enumerate(nums[i+1:]):
                if num_i + num_j == target:
                    return [i,i+1+j]
        return []

Two hash dictionary method

When solving solution 1, we found that we have to match the nums[i] in the first cycle with all the following numbers once, which takes a lot of time We consider whether we can find two numbers whose sum is target in one traversal Here, we use the hash table to store the currently accessed numbers. Each time we go to a new number, we check whether there is a number with the value of target num [i] in the hash table. If so, it will be returned

Solution II C + + implementation

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        map<int,int> hash;
        int len = nums.size();
        for(int i = 0 ; i < len ; i++){
            int index = hash[target - nums[i]];
            if(index != 0 && index-1 != i){
               return {i,index-1};
            }
            hash[nums[i]] = i + 1;// To prevent confusion between subscript 0 and subscript 0, i+1 is used here
        }
        return {};
    }
};

Implementation of algorithm 2 in python

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        hash = {}
        for i,num_i in enumerate(nums):
            if target-num_i in hash.keys() and hash[target-num_i] != i:
                return [i,hash[target-num_i]]
            hash[num_i] = i
        return []