Hello everyone, I’m Coding bear, today is the first day of LeetCode’s daily problem, today you are better than yesterday!

The question

Given an integer array nums and an integer target, find the two integers in the array whose sum is target and return their array indices.

You can assume that there is only one answer for each input. However, the same element in the array must not appear repeatedly in the answer.

You can return the answers in any order.

The sample

Input: nums = [2,7,11,15], target = 9 output: [0,1] description: because nums[0] + nums[1] == 9, return [0,1].Copy the code

Answer key

Methods a

If A+B=target, then A+B=target, then A+B=target, then A+B=target, then A+B=target, then A+B=target. If A and B are not the same number of positions and A+B=target, we have found the two positions for the answer.

for (int i = 1; i <= n; i++) {
    for (int j = 1; j < i; j++) {
        Nums [I]+nums[j]=target}}Copy the code

Time complexity: O(n2)O(n^2)O(n2)

Space complexity: O(1)O(1)O(1)

Method 2

So based on the premise of method one, let’s think about it can we have lower time complexity? So we’ve fixed A, and we’ve gone through the array looking for B to see if there’s A+B=target, so can we speed up the search for B?

A+B=target can be viewed as B= target-a, so we can fix A and check if there is A B that satisfies B= target-a. Quickly retrieve an index of data that can be hashed in a table. In this case, we can use the value of the array as the key of the hash table, and the index as the value.

In C++, map is based on red-black tree. The time complexity of insertion and query is O(logn)O(logn)O(logn). The bottom layer of unORDER_map is based on the hash table, and the insertion and query time complexity is O(1)O(1)O(1). Therefore, the unorder_map implementation is chosen.

Time complexity: O(n)O(n)O(n)

Space complexity: O(n)O(n)O(n)

C + + code

class Solution {
public:
    unordered_map<int.int> numExist;
    vector<int> twoSum(vector<int> &nums, int target) {
      vector<int> ans;
      for (int i = 0; i < nums.size(a); i++) {int b = target - nums[i];
        if (numExist.count(b)) {
          ans.push_back(i);
          ans.push_back(numExist.at(b));
          break;
        }
        numExist[nums[i]] = i;
      }
      returnans; }};Copy the code

Java code

class Solution {
    public int[] twoSum(int[] nums, int target) {
        HashMap<Integer, Integer> numExist = new HashMap<Integer, Integer>();
        for (int i = 0; i < nums.length; ++i) {
            if (numExist.containsKey(target - nums[i])) {
                return new int[]{i, numExist.get(target - nums[i])};
            }
            numExist.put(nums[i], i);
        }
        return new int[2]; }}Copy the code

Title link: https://leetcode-cn.com/problems/two-sum/

I am a programming bear, committed to making everyone a better person, welcome to “follow”, “like”, “retweet” support ~